Linux内核设计与实现

书中内容基于 kernel-2.6.34 版本内核，书籍名《Linux内核设计与实现》

Linux内核简介

kernel许可协议

linux kernel 基于 (GPL v2)作为限制条款，保障每个人都可以自由获取、修改内核，但是也要让得到你修改内核的人同时也享有你曾经享有的权利——开源全部源代码。

从内核出发

内核源码树

配置内核

1. make config
2. make menuconfig
3. make gconfig
4. make defconfig：基于默认配置来编译内核
5. make oldconfig：基于已有配置来编译内核

编译内核

安装内核

安装内核模块

生成initramfs

更新引导

编译内核时候会在内核代码根目录下创建一个 System.map 文件，这是一份符号对照表，用来将内核符号和他们的起始地址对应起来，调试时候用来把内存地址翻译成容易理解的函数名和变量名。

内核开发的特点

• 内核编程时候既不能访问C库，也不能访问标准的C头文件(常用C库函数在linux内核中已经被实现)
• 内核编程时候必须使用 GNU C。
• 内核编程时缺乏用户空间那样的内存保护机制。
• 内核编程时候难以执行浮点运算。
• 内核给每个进程只有一个很小的定长堆栈。
• 由于内核支持异步中断、抢占和SMP，因此必须时刻注意同步和并发。
• 要考虑可移植性

Kernel头文件使用

• 基本的头文件位于内核源码顶级目录下的include 目录中。例如：头文件<linux/inotify.h>对应内核源码树中的include/linux/inotify.h
• 体系结构相关的头文件集位于内核源代码树的 arch/<archiecture>/include/asm目录下。梅核代码通过以 asm/为前缀的方式包含这些头文件，例如：<asm/ioctl.h>

kernel 打印日志

内核中无printf()函数，但是它提供了printk()，printk()负责把格式化好的字符串拷贝到内核日志缓冲区上，printf()和printk()之间的一个显著区别在于，printk()允许你通过指定一个标志来设置优先级。syslogd会根据这个优先级标志来决定在什么地方显示这条系统信息。

1

printk(KERN_ERR "this is an error\n");

GNU C

Linux内核是用C语言编写的，但是内核不完全符合ANSIC标准，只要有可能，内核开发者总是要用到 gcc 提供的多语言扩展部分(gcc是多种GNU编译器的集合，它包含的C编译器既可以编译内核，也可以编译Linux系统上用C语言写的其它代码)。

内核开发者使用的C语言涵盖了ISO C99标准和GNU C扩展特性，最早只有 gcc 提供足够多的扩展特性，才可以用来编译linux内核。

以下是一些内核代码中使用到的C语言扩展部分：

内联函数(inline)

C99 和 GNU C 都支持内联函数。函数会在调用位置展开，消除函数调用和返回带来的开销(寄存器存储和恢复)。不过也有缺点，这会导致代码变长，意味着占用更多的内存空间或者占用更多的指令缓存。内核开发者通常把那些对事件要求比较高，本身长度又比较短的函数定义成内联函数。如果一个函数较大，会被反复调用，且没有特别的时间上的限制，我们不赞成把它做成内联函数。

定义一个内联函数时候，需要使用static作为关键字，并且用inline限定它。比如：static inline void wolf(unsigned long tail_size);

内核中，为了类型安全和易读性，有限使用内联函数，而不是复杂的宏。

汇编内联

gcc 编译器支持在C函数中嵌入汇编指令。当然在内核编程的时候，只有知道对应的体系结构才能使用这个功能。

通常使用 asm() 指令嵌入汇编代码，例如：

1
2

unsigned int low, high; // low 和 high 分别包含64位时间戳的低32位和高32位
asm volatile("rdtsc" : "=a" (low), "=d" (high));

Linux 内核混合使用了C语言和汇编语言。在偏近体系结构的底层或对执行事件要求严格的地方，一般使用的是汇编语言。而内核其它部分的大部分代码是用C语言编写的。

分支声明

对于条件选择语句，gcc内建了一条指令用于优化，在一个条件经常出现，或者该条件很少出现的时候，编译器可以根据这条指令对条件分支选择进行优化。内核把这条指令封装成了宏，比如likely()和unlikely()，这样使用起来比较方便。

例如下面是一个条件选择语句：

1
2
3

if (error) {
    /* ... */
}

如果想要把这个选择标记成绝少发生的分支：

1
2
3
4

// 我们认为 error 绝大部分事件都会是0
if (unlikely(error)) {
    /* ... */
}

如果想要把一个分支标记位通常为真的选择：

1
2
3
4

// 我们认为 success 通常都不会为0
if (likely(success)) {
    /* ... */
}

在使用这两个宏之前，一定要搞清楚这个条件，如果判断不准确，那么性能反而会下降。

没有内存保护机制

如果用户程序访问非法内存，内核会发现这个错误，发送 SIGSEGV 信号，并结束整个进程。

如果内核自己非法访问内存，就会导致 oops，且结果很难控制。

另外内核中的内存并不分页，也就是说，你每用掉一个字节，物理内存就减少一个字节。所以，在你想往内核里加入新功能时候要记住这一点。

不要轻易在内核中使用浮点数

在用户空间的进程内使用浮点操作的时候，内核会完成从整数操作模式到浮点数操作模式转换。在执行浮点指令时候因体系结构不同，内核的选择也不同，但是，内核通常捕获陷阱并着手于整数到浮点方式的转变。

与用户空间进程不同，内核并不能完美地支持浮点操作，因为它本身不能陷入。在内核中使用浮点数时候，除了要人工保存和恢复浮点寄存器，还有其它一些琐碎的事情要做。如果要直截了当的回答，那就是：别这样做，除非一些极少情况，否则别在内核中使用浮点操作。

容积小而固定的栈

用户空间的程序可以从栈上分配大量的空间来存放变量，甚至巨大的结构体或者是包含数以千计的数据项的数组都没问题。之所以可以这么做，是因为用户空间的栈本身比较打，而且还能动态增长。

内核堆栈的准确大小随体系结构而变。在 X86 上，栈的大小在编译时候配置，可以是 4KB 也可以是 8KB。

历史上说，内核栈的大小是两页，32位机器内核栈是 8KB，而 64位机器是 16KB，这个固定不变的，每个处理器都有自己的栈。

同步和并发

内核很容易产生竞争条件。和单线程的用户空间程序不同，内核的许多特性都要求能够并发地访问共享数据，这就要求有同步机制以保证不出现竞争条件，特别是：

• Linux是抢占多任务操作系统。内核的进程调度程序即兴对进程进行调度和重新调度。内核必须和这些任务同步。
• Linux内核支持对称多处理器系统(SMP)。所以，如果没有适当的保护，同时在两个或两个以上的处理器上执行的内核代码很可能会同时访问共享的同一个资源。
• 中断是异步到来的，完全不顾及当前正在执行的代码。也就是说，如果不加以适当的保护，中断完全有可能在代码访问资源的时候到来，这样，中断处理程序就有可能访问同一资源。
• Linux内核可以抢占。所以，如果不加以适当的保护，内核中一段正在执行的代码可能会被另外一段代码抢占，从而有可能导致几段代码同时访问相同的资源。

常用的解决竞争的办法是自旋锁和信号量。

可移植性的重要性

大部分 C 代码应该与体系结构无关，在许多不同体系结构的计算机上都能编译和执行，因此，必须把与体系结构相关的代码从内核代码树的特定目录中适当地分离出来。

诸如保持字节序、64位对齐、不假定字长和页面长度等一系列准则都有助于移植性。

进程管理

• 进程定义和相关概念，比如：线程
• Linux内核如何管理进程
• 进程在内核中的生命周期

进程管理是整个操作系统的心脏所在

进程

进程是处于执行期的程序(目标码存放在某种介质上)。但进程并不仅仅局限于一段可执行程序代码(Unix称其为代码段，text section)。通常进程还要包含其它资源， 像打开的文件、挂起的信号，内核内部数据，处理器状态，一个或多个具有内存映射的内存地址空间及一个或多个执行线程，当然还包括用来存放全局变量的数据段等。 实际上，进程就是正在执行的程序代码的实时结果。内核需要有效而又透明的管理所有细节。

执行线程，简称线程，是在进程中活动的对象。每个线程都拥有一个独立的程序计数器、进程栈和一组进程寄存器。内核调度的对象是线程，而不是进程。 在传统的Unix系统中，一个进程只包含一个线程，但现在的系统中，包含多个线程的多线程程序司空见惯。对Linux而言，并不特别区分线程和进程。

在现代操作系统中，进程提供两种虚拟机制：虚拟处理器和虚拟内存。虽然实际上可能是许多进程正在分享一个处理器，但是虚拟处理器给进程一个假象， 让这些进程觉得自己在独享处理器。

程序不是进程，进程是处于执行期间程序及其相关资源的总称。

Linux通过调用 fork() 复制一个现有进程来创建一个全新的进程。调用 fork() 的进程称为父进程，新产生的进程称为 子进程。在调用结束时候， 在返回点这个相同位置上，父进程恢复执行，子进程开始执行。 fork() 系统调用从内核返回两次：一次回到父进程，另一次回到新产生的子进程。

通常，创建新的进程都是为了立即执行新的、不同的程序，接着调用 exec() 这组函数就可以创建新的地址空间，并把新的程序载入其中。 在现代 Linux 内核中， fork() 实际上是由 clone() 系统调用完成的，后者将在后面讨论。

最终，程序通过 exit() 系统调用退出执行。这个函数会终结进程并将其占用的资源释放掉。父进程可以通过 wait() 系统调用查询子进程是否终结， 这其实使得进程拥有了等待特定进程执行完毕的能力。进程退出执行后被设置为僵死状态，直到它的父进程调用 wait() 或者 waitpid() 为止。

注意：进程的另一个名字是 任务。Linux 内核通常把进程也叫做任务，两个术语是一样的。

进程描述符及任务结构

内核把进程的列表存放在叫做任务队列(task list)的双向循环列表中。链表中的每一项都是类型为 task_struct、称为进程描述符的结构，该结构定义在 <linux/sched.h> 文件中。进程描述符中包含一个具体进程的所有信息。

task_struct 相对较大，在 32 位机器上，它大约有 1.7KB。但如果考虑到该结构内包含了内核管理一个进程所需的所有信息，那么它的大小也就算 相当小了。进程描述符中包含的数据能完整描述一个正在执行的程序：此进程打开的文件、进程的地址空间、挂起的信号、进程的状态、还有其它更多信息。

分配进程描述符

Linux 通过 slab 分配器分配 task_struct 结构，这样能达到对象复用和缓存着色的目的。在 2.6 以前的内核中，各个进程的 task_struct 存放在它们内核栈的尾端。这样做是为了让那些像X86那样寄存器较少的硬件体系结构只要通过栈指针就能计算出它的位置，从而避免使用额外的寄存器专门记录。 由于现在用 slab 分配器动态生成 task_struct，所以只需在栈底(对于向下增长的栈来说)或栈顶(对于向上增长的栈来说)创建一个新的结构 struct thread_info 在 x86 上， struct thread_info在文件 <asm/thread_info.h>中定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct thread_info {
    struct task_struct*         task;
    struct exec_domain*         exec_domain;
    __u32                       flags;
    __u32                       status;
    __u32                       cpu;
    int                         preempt_count;
    mm_segment_t                addr_limit;
    struct restart_block        restart_block;
    void*                       sysenter_return;
    int                         uaccess_err;
};

每个任务的 thread_info 结构在它的内核栈的末尾端分配。结构中 task 域中存放的是指向该任务实际 task_struct 的指针。

通过预先分配和重复使用 task_struct，可以避免动态分配和释放带来的资源消耗。

寄存器较弱的体系结构不是引入 thread_info 结构的唯一原因。这个新建的结构使在汇编代码中计算其偏移变得非常容易。

进程描述符的存放

内核通过一个唯一的进程标识值(process identification value) 或 PID 来标识每个进程。PID 是一个数，标识为 pid_t 隐含类型(隐含类型标识隐藏了该类型实现，用句柄替代类型实现)， 实际上就是一个int类型。为了与老版本的Unix和Linux兼容，PID 的最大值默认设置为 32768 (short int 短整型的最大值)，当然这个值也可以增加到 400万(受 <linux/threads.h> 中所定义PID最大值的限制)。

内核把每个进程 PID 存放在它们各自的进程描述符中。

PID 最大值表明了系统中允许同时存在的进程的最大数目。32768一般来说够用了，而且这个值越小，进程调度一圈就越快。

在内核中，访问任务/进程通常需要获得指向其 task_struct 的指针。实际上，内核中大部分处理进程的代码都是直接通过 task_struct 进行的。因此，通过 current 宏查找到当前正在运行进程的进程描述符的速度就显得尤为重要。硬件体系结构不同， 该宏的实现也不同，它必须针对专门的硬件体系结构做处理。有的硬件体系结构可以拿出一个专门寄存器来存放指向当前进程 task_struct 的指针，用于加快访问速度。而有些像x86这样的体系结构(其寄存器并不富余)，就只能在内核栈的尾端创建 thread_info 结构，通过计算偏移间接地查找 task_struct 结构。

在 X86 系统上，current 把栈指针的后 13 个有效位屏蔽掉，用来计算出 thread_info 的偏移。该操作是通过 current_thread_info() 函数完成的。汇编代码如下：

1
2

mov1 $-8192, %eax
andl %esp, %eax

这里假定栈的大小为 8KB。当 4KB 的栈启用时候，就要用 4096，而不是 8192.

最后，current再从 thread_info 的 task 域中提取并返回 task_struct 的地址：

1

current_thread_info()->task;

对比一下这部分在 PowerPC (IBM基于RISC 的现代微处理器)，我呢把可以发现 PPC 当前的 task_struct 是保存在一个寄存器中。 也就是说，在 PPC 上， current 宏只需要把 r2 寄存器中的值返回就行了。与 X86 不一样，PPC 有足够多的寄存器，所以它的实现有这样选择的余地。 而访问进程描述符是一个重要的频繁操作，所以 PPC 的内核开发者觉得完全有必要为此使用一个专门的寄存器。

进程状态

进程描述符中的 state 域描述了进程的当前状态。系统中的每个进程都必然处于五种进程状态中的一种。该域的值也必为以下五种状态标识之一：

• TASK_RUNNING(运行) —— 进程是可执行的：它或者正在执行，或者在运行队列中等待执行。这是进程在用户空间中执行的唯一可能的状态；这种状态也可以应用到内核空间中正在执行的进程。
• TASK_INTERRUPTIBLE(可中断) —— 进程正在睡眠(也就是说它被阻塞)，等待某些条件的达成。一旦这些条件达成，内核就会把 进程状态设置为可运行。处于此状态的进程也会因为接收到信号而提前被唤醒并随时准备投入运行。
• TASK_UNINTERRUPTIBLE(不可中断) —— 除了就算是接收到信号也不会被唤醒或者准备投入运行外，这个状态与可打断状态相同。这个状态通常在进程必须等待时不受干扰或等待事件很快就会发生时候出现。由于处于此状态的任务对信号不做响应，所以较之可中断状态使用的比较少。
• __TASK_TRACED —— 被其它进程跟踪的进程，例如通过 ptrace 对调试程序进行跟踪。
• __TASK_STOPPED(停止) —— 进程停止执行；进程没有投入运行也不能投入运行。通常这种状态发生在接收到 SIGSTOP、SIGTSTP、SIGTTOU 等信号的时候，此外在调试期间收到任何信号，都会使进程进入这种状态。

设置当前进程状态

内核经常需要调整某个进程的状态。这时最好使用 set_task_state(task, state) 函数：

1

set_task_state(task, state);    // 将任务 task 的状态设置为 state

该函数将指定的进程设置为指定状态。必要的时候下，它会设置内存屏障来强制其它处理器做重新排序(一般只有在 SMP 系统中有此必要)。否则，它等价于：

1

task->state = state;

set_current_state(state) 和 set_task_state(current, state) 含义是等同的。参看 <linux/sched.h> 中相关函数的说明。

进程上下文

可执行程序代码是进程的重要组成部分。这些代码从一个可执行文件载入到进程的地址空间执行。一般程序在用户空间执行。当一个程序执行了系统调用或者触发了某个异常，它就陷入了内核空间。 此时，我们称内核 “代表进程执行”并处于进程上下文中。在此上下文中 current 宏是有效的。除非在此间隙有更高优先级的进程需要执行并由调度器做出了相应调整，否则在内核退出的时候，程序恢复在用户空间会继续执行。

系统调用和异常处理程序是对内核明确定义的接口。进程只有通过这些接口才能陷入内核执行 —— 对内核的所有访问都必须通过这些接口。

进程家族树

Unix 系统的进程之间存在一个明显的继承关系，在linux系统中也是如此。所有的进程都是 PID 为 1 的 init 进程的后代。 内核在系统启动的最后阶段启动 init 进程。该进程读取系统的初始化脚本(initscript) 并执行其它的相关程序，最终完成系统启动的整个过程。

系统中的每个进程必有一个父进程，每个进程也可以拥有零个或多个子进程。拥有同一个父进程的所有进程都被称为兄弟。进程的关系存放在进程描述符中。每个 task_struct 都包含一个指向其父进程的 task_struct、叫做 parent 的指针，还包含一个称为 children 的子进程链表。所以，对于 当前进程，可以通过下面的代码获得其父进程的进程描述符：

1

struct task_struct*         myParent = current->parent;

同样，也可以按以下方式依次访问子进程：

1
2
3
4
5
6
7

struct task_struct* task;
struct list_head* list;

list_for_each(list, &current->children) {
    task = list_entry(list, struct task_struct, sibling);
    /* task 现在指向当前的某个子进程 */
}

init 进程的描述符是作为 init_task 静态分配的。下面的代码可以很好的演示所有进程之间的关系：

1
2
3
4

struct task_struct* task;
for (task = current; task != &init_task; task = task->parent) {
    // task 现在指向 init
}

实际上，你可以通过这种继承体系从系统的任何一个进程出发查找到任意指定的其它进程。但大多数时候，只需要通过简单的重复的方式就 可以遍历系统中的所有进程。这非常容易做到，因为一个任务队列本来就是一个双向的循环链表。对于给定的进程，获取链表中的下一个进程：

1

list_entry(task->tasks.next, struct task_struct, tasks)

获取前一个进程的方法与之相同：

1

list_entry(task->tasks.prev, struct tsak_struct, tasks)

这两个例程分别通过next_task(task)宏和prev_task(task)宏实现。而实际上，for_each_process(task)宏提供了依次访问整个任务队列的能力。 每次访问，任务指针都指向链表中的下一个元素：

1
2
3
4
5
6

struct task_struct* task;

for_each_process(task) {
    // 它打印出每一个任务的名称和PID
    printk("%s [%d]\n", task->comm, task->pid);
}

在一个拥有大量进程的系统中通过重复来遍历所有进程的代价是很大的。因此，如果没有必须这样做的理由，不要这样做。

进程创建

Unix 的进程创建很特别。许多其它的操作系统都提供了产生(spawn)进程的机制，首先在新的地址空间里创建进程，读入可执行文件，最后开始执行。

Unix采用了与众不同的实现方式，它把上述步骤分解到两个单独的函数中去执行： fork() 和 exec()。

首先， fork() 通过拷贝当前进程创建一个子进程。子进程与父进程的区别仅仅在于 PID(每个进程唯一)、PPID(父进程的进程号，子进程将其设置为被拷贝进程的PID) 和某些资源和统计量(例如，挂起的信号，它没有必要被继承)。

exec()函数负责读取可执行文件并将其载入地址空间开始运行。把这两个函数组合起来使用的效果跟其它系统使用的单一函数的效果相似。

写时拷贝

传统的 fork() 系统调用直接把所有资源复制给新创建的进程。这种实现过于简单且效率低下，因为它拷贝的数据也许并不共享，更糟糕的是，如果新进程打算立即执行一个新的映像，那么所有的拷贝都将前功尽弃。 Linux 的 fork() 十一鸥鸟更写时拷贝页实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝。

只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行，在此之前，只是以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候才进行。 在页根本不会被写入的情况下(距离来说，fork()后立即调用exec())他们就无需复制了。

fork()的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符。在一般情况下，进程创建后会马上运行一个可执行文件，这种优化可以避免拷贝大量根本都不会被使用的数据(地址空间里常常包含数十兆的数据)。 由于Unix强调进程快速执行的能力，所以这个优化是很重要的。

fork()

Linux 通过 clone() 系统调用实现 fork()。这个调用通过一系列的参数标志来指明父、子进程需要共享的资源。 fork()、vfork()和__clone()库函数都根据各自需要的参数标志去调用 clone()，然后由 clone() 去调用 do_fork()。

do_fork()完成创建中的大部分工作(定义在 kernel/fork.c 中)，该函数调用 copy_process() 函数，然后让进程开始运行。 copy_process()完成以下主要工作：

1. 调用 dup_task_struct() 为新进程创建一个内核栈、thread_info 结构和 task_struct，这些值与当前进程的值相同。此时，子进程和父进程的描述符是完全相同的。
2. 检查并确保新创建这个子进程后，当前用户拥有的进程数目没有超出给它分配的资源的限制。
3. 子进程着手使自己与父进程区别开来。进程描述符内的许多成员都要被清零或设为初始值。那些不是继承而来的进程描述符成员，主要是统计信息。task_struct中的大多数数据都依然未被修改。
4. 子进程的状态被设置为 TASK_UNINTERRUPTIBLE，以保证它不会投入运行。
5. copy_process()调用 copy_flags() 以更新 task_struct 的 flags 成员。表明进程是否拥有超级用户权限的 PF_SUPERPRIV标志被清零。表明进程还没有调用 exec() 函数的 PF_FORKNOEXEC 标志被设置。
6. 调用 alloc_pid() 为新进程分配一个有效的 PID。
7. 根据传递给 clone() 的参数标志，copy_process()拷贝或共享打开的文件、文件系统信息、信号处理函数、进程地址空间和命名空间等。 在一般情况下，这些资源会被给定进程的所有线程共享；否则，这些资源对每个进程是不同的，因此被拷贝在这里。
8. 最后，copy_process()做收尾工作并返回一个指向子进程的指针。

再回到 do_fork()函数，如果 copy_process() 函数返回成功，新创建的子进程被唤醒并让其投入运行。内核有意选择子进程首先执行。因为一般子进程都会马上调用 exec()函数，这样可以避免写时拷贝的额外开销，如果父进程首先 执行的话，有可能会开始向地址空间写入。

vfork()

除了不拷贝父进程的页表项外，vfork()系统调用和fork()的功能相同。子进程作为父进程的一个单独的线程在它的地址空间里运行，父进程被阻塞，直到子进程退出或执行 exec()。子进程不能向地址空间写入。在过去的 3BSD 时期，这个优化是有意义的，那时并未使用写时拷贝页来实现 fork()。现在由于在执行fork()十引入了写时拷贝页而且明确了子进程先执行，vfork()的好处就仅限于不拷贝父进程的页表项了。 如果 Linux 将来fork()有了写时拷贝页表项，那么vfork()就彻底没用了。另外由于vfork()语义非常微妙(试想，如果exec()调用失败会发生什么)， 所以理想情况下，系统最后不要调用 vfork()，内核也不用实现它。完全可以把 vfork() 实现成一个普普通通的 fork() —— 实际上，Linux2.2以前就是这么做的。

vfork()系统调用的实现是通过向 clone() 系统调用传递一个特殊标志来进行的。

1. 在调用 copy_process() 时候，task_struct 的 vfork_done成员被设置为 NULL。
2. 在执行 do_fork() 时，如果给定特别标志，则 vfork_done会指向一个特定地址。
3. 子进程先开始执行后，父进程不是马上恢复执行，而是一直等待，直到子进程通过vfork_done指针向他发送信号。
4. 在调用 mm_release() 时候，该函数用于进程退出内存地址空间，并且检查 vfork_done 是否为空，如果不为空，则会向父进程发送信号。
5. 回到 do_fork()，父进程醒来并返回。 如果一切执行顺利，子进程在新的地址空间里运行而父进程也恢复了在原地址空间的运行。这样，开销确实降低了，不过它的实现并不是优良的。

线程在Linux中的实现

线程机制是现代编程技术中非常常用的一种抽象概念。该机制提供了在同一个程序内共享内存地址空间运行的一组线程。这些线程还可以共享打开的文件和其它资源线程机制支持并发程序设计技术，在多处理器系统上，它也能保证真正的并行处理。

Linux 实现线程的机制非常独特。从内核角度来说，它并没有线程这个概念。Linux把所有的线程都当作进程来实现。内核并没有准备特别的调度算法或者定义特别的数据结构来表征线程。 相反，线程仅仅被视为一个与其它进程共享某些资源的进程。每个线程都拥有唯一隶属于自己的 task_struct，素以在内核中，它看起来就像是一个普通的进程 (只是线程和其它一些进程共享某些资源，如地址空间)。

上述线程机制的实现与Windows 或是 Sun Solaris 等操作系统的实现差异非常大。这些系统都在内核中提供了专门支持线程的机制(这写系统常常把线程称作轻量级进程)。 “轻量级进程”这种叫法本身就概括了Linux在此处与其它系统的差异。

在其它系统中，相较于重量级的进程，线程被抽象成一种耗费较少资源，运行迅速的执行单元。而对于linux来说，它只是一种进程间共享资源的手段(Linux进程本身就够轻量级的来)。 举个例子来说，假如我们有一个包含四个线程的进程，在提供专门线程支持的系统中，通常会有一个包含指向四个不同线程的指针的进程描述符。 该描述符负责描述像地址空间、打开的文件这样的共享资源。线程本身再去描述它独占的资源。相反，Linux仅仅创建四个进程并分配四个普通的 task_struct结构。建立这四个进程时候指定他们共享某些资源，这是相当高雅的做法。

创建线程

线程的创建和普通进程的创建类似，只不过在调用 clone() 的时候需要传递一些参数标志来指明需要共享的资源：

1

clone(CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND, 0);

上面的代码产生的结果和调用fork()差不多，只是父子俩共享地址空间、文件系统资源、文件描述符和信号处理程序。换个说法就是，新建的进程和它的父进程就是流行的所谓线程。

对比以下，一个普通的 fork() 的实现是：

1

clone(CLONE_VFORK|CLONE_VM|SIGCHLE, 0);

传递给 clone() 的参数标志决定了新创建进程的行为方式和父子进程之间共享的资源种类。 表3-1列举了这些clone()用到的参数标志以及他们的作用，这些是在<linux/sched.h>中定义的。

内核线程

内核经常需要在后台执行一些操作。这种任务可以通过内核线程完成 —— 独立运行在内核空间的标准进程。

内核线程与普通进程间的区别在于内核线程没有独立的地址空间(实际上指向地址空间的mm指针被设置为NULL)。 它们只在内核空间运行，从来不切换到用户空间去，内核进程和普通进程一样，可以被调度，也可以被抢占。

Linux确实会把一些任务交给内核线程去做，像flush和ksofirqd这些任务就是明显的例子。

内核线程是在系统启动时候由其它内核线程创建。内核是通过从kthreadd内核进程中衍生出所有新的内核线程来自动处理这一点的。在 <linux/kthread.h>中声明有接口，于是，从现有内核线程中创建一个新的内核线程的方法如下：

1

struct task_struct* kthread_create (int (*threadfn) (void* data), void* data, const char namefmt[], ...)

新的任务是由 kthread 内核进程通过 clone()系统调用而创建的。新的进程将运行 threadfn 函数，给其传递的参数是data。 进程会被命名为 namefmt, namefmt接受可变参数列表类似于 printf() 的格式化参数。新创建的进程处于不可运行状态，如果不通过调用 wake_up_process()明确地唤醒它，它不会主动运行。创建一个进程并让它运行起来，可以通过调用 kthread_run()来达到：

1

struct task_struct* kthread_run (int (*threadfn) (void* data), void* data, const char namefmt[], ...)

这个例程是以宏实现的，只是简单地调用了 kthread_create() 和 wake_up_process()：

1
2
3
4
5
6
7
8

#define kthread_run(threadfn, data, namefmt, ...)               \
({                                                              \
    struct task_struct* k;                                      \
    k = kthread_create(threadfn,data,namefmt,## __VA_ARGS__);   \
    if (!IS_ERR(k))                                             \
        wake_up_process(k);                                     \
    k;                                                          \
})

内核线程启动后就一直运行直到调用 do_exit() 退出，或者内核的其它部分调用 kthread_stop()退出，传递给 kthread_stop()的参数为kthread_create()函数返回的 task_struct结构的地址：

1

int kthread_stop(struct task_struct* k);

进程终结

进程终结时候，内核必须释放它所占有的资源，并把这一消息告知父进程。

一般来说，进程的析构是自身引起的。它发生在进程调用exit()系统调用时候，既可能显示地调用这个系统调用，也可能显示地从某个程序的主函数返回 (其实C语言编译器会在main()函数的返回点后面放置调用exit()的代码)。当进程接受到它既不能处理也不能忽略的信号或异常时候，它还可能主动被终结。不管进程是怎么终结的，该任务 大部分要靠do_exit()(定义于kernel/exit.c)来完成，它要做下面这些繁琐工作：

1. 将 task_struct 中的标志成员设置为 PF_EXITING
2. 调用 del_timer_sync() 删除任一内核定时器。根据返回的结果，它确保没有定时器在排队，也没有定时器处理程序在运行。
3. 如果 BSD 的进程记账功能是开启的，do_exit() 调用 acct_update_integrals() 来输出记账信息。
4. 然后调用 exit_mm()函数释放进程占用的 mm_struct，如果没有别的进程使用它们(也就是说，这些地址空间没有被共享)，就彻底释放它们。
5. 接下来调用 sem_exit() 函数。如果进程排队等候 IPC 信号，它则离开队列。
6. 调用 exit_files() 和 exit_fs()，以分别递减文件描述符、文件系统数据的引用计数。如果某个引用计数值为0，那么就代表没有进程在使用相应的资源，此时可以释放。
7. 接着把存放在 task_struct 的 exit_code 成员中的任务退出代码置为由 exit() 提供的退出代码，或者去完成任何其它由内核机制规定的退出动作。退出代码存放在这里供父进程随时检索。
8. 调用 exit_notify() 向父进程发送信号，给子进程重新找养父，养父为线程组中的其它线程或者为 init 进程，并把进程状态(存放在task_struct结构的 exit_state中)设成 EXIT_ZOMBIE。
9. do_exit()调用 schedule() 切换到新的进程。因为处于 EXIT_ZOMBIE 状态的进程不会再被调度，所以这时进程所执行的最后一段代码。do_exit() 永不返回。

至此，与进程相关联的所有资源都被释放掉了(假设该进程是这些资源的唯一使用者)。进程不可运行(实际上也没有地址空间让他运行)并处于EXIT_ZOMBIE 退出状态。它占用的所有内存就是内核栈、thread_info结构和task_struct结构。此时进程存在的唯一目的就是向它的父进程提供信息。父进程检索到信息后，或者通知内核那是无关的信息后，由进程所持有的剩余内存被释放，归还给系统使用。

删除进程描述符

在调用了 do_exit() 之后，尽管线程已经僵死不能再运行了，但是系统还是保留了它的进程描述符。前面说过，这样做可以让系统有办法在子进程终结后仍然获得它的信息。因此，进程终结时候所需的清理工作和进程描述符的删除被分开执行。 在父进程获得已终结的子进程的信息后，或者通知内核它并不关注那些信息后，子进程的task_struct结构才被释放。

wait()这一族函数都是通过唯一(但是很复杂)的一个系统调用 wait4()来实现的。它的标准动作是挂起调用它的进程，直到其中的一个子进程退出，此时函数会返回该子进程的PID。 此外，调用该函数时候提供的指针会包含子函数退出时候的退出码。

当最终需要释放进程描述符时候，release_task()会被调用，用以完成以下工作：

1. 它调用 __exit_signal()，该函数调用__unhash_process()，后者又调用 detach_pid() 从 pidhash 上删除该进程，同时也要从任务列表中删除该进程。
2. _exit_signal()释放目前僵死进程所使用的所有剩余资源，并进行最终统计和记录。
3. 如果这个进程是线程组最后一个进程，并且领头进程已经死掉，那么 release_task() 就要通知僵死的领头进程的父进程。
4. release_task() 调用put_task_struct()释放进程内核栈和thread_info结构所占的页，并释放task_struct所占的 slab 高速缓存。

至此，进程描述符和所有进程独享的资源全部被释放掉。

孤儿进程造成的进退维谷

如果父进程在子进程之前退出，必须有机制来保证子进程能找到一个新的父亲，否则这些成为孤儿的进程就会在退出时候永远处于僵死状态，白白地耗费内存。 前面的部分已经有所暗示，对于这个问题，解决方法是给子进程在当前线程组内找一个线程作为父亲，如果不行，就让 init 做它们的父进程。在 do_exit() 中会调用 exit_notify()，该函数会调用 forget_original_parent()，而后者会调用 find_new_reaper() 来执行寻父过程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static struct task_struct* find_new_reaper (struct task_struct* father)
{
    struct pid_namespace* pid_ns = task_active_pid_ns (father);
    struct task_struct* thread;
    
    thread = father;
    while_each_thread(father, thread) {
        if (thread->flags & PF_EXITING)
            continue;
        if (unlikely(pid_ns->child_reaper == father))
            pid_ns->child_reaper = thread;
        return thread;
    }
    
    if (unlikely (pid_ns->child_reaper == father)) {
        write_unlock_irq (&tasklist_lock);
        if (unlikely(pid_ns == &init_pid_ns))
            panic ("Attempted to kill init!");
        zap_pid_ns_processes (pid_ns);
        write_lock_irq(&tasklist_lock);
        
        pid_ns->child_reaper = init_pid_ns.child_reaper;
    }
    return pid_ns->child_reaper;
}

这段代码试图找到进程所在线程组内的其它进程。如果线程组内没有其它进程，他就找到并返回的是 init 进程。现在，给子进程找到合适的养父进程来， 只需遍历所有子进程并为它们设置新的父进程：

1
2
3
4
5
6
7
8
9

reaper = find_new_reaper(father);
list_for_each_entry_safe(p, n, &father->children, sibling) {
    p->real_parent = reaper;
    if (p->parent == father) {
        BUG_ON(p->ptrace);
        p->parent = p->real_parent;
    }
    reparent_thread(p, father);
}

然后调用 ptrace_exit_finish() 同样进行新的寻父过程，不过这次是给 ptraced 的子进程寻找父亲。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void exit_ptrace(struct task_struct* tracer)
{
    struct task_struct *p, *n;
    LIST_HEAD(ptrace_dead);
    
    write_lock_irq(&tasklist_lock);
    list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
        if (__ptrace_detach(tracer, p)) {
            list_add (&p->ptrace_entry, &ptrace_dead);
        }
    }

    write_unlock_irq(&tasklist_lock);
    BUG_ON(!list_empty(&tracer->ptraced));

    list_for_each_entry_safe(p, n, &ptrace_dead, ptrace_entry) {
        list_del_init(&p->ptrace_entry);
        release_task(p);
    }
}

这段代码遍历了两个链表：子进程链表和ptrace子进程链表，给每个子进程设置新的父进程。这两个链表同时存在的原因很有意思，它也是2.6内核的一个新特性。 当一个进程被跟踪时，它的临时父亲设定为调试进程。此时如果它的父进程退出了，系统会为它和它的所有兄弟重新找一个父进程。在以前的内核中，这就需要遍历系统所有 的进程来找这些子进程。现在的解决方法是在一个单独的被ptrace跟踪的子进程链表中搜索相关的兄弟进程 —— 用两个相对较小的链表减轻了遍历带来的消耗。

一旦系统为进程成功地找到和设置了新的父进程，就不会再有出现驻留僵死进程的危险了。init进程会例行调用wait()来检查其子进程，清除所有与其相关的僵死进程。

小结

本章主要考察了系统中的核心概念 —— 进程。讨论了进程的一般特性，它为何如此重要，以及进程和线程之间的关系

讨论了Linux如何存放和表示进程(task_struct和thread_info)，如何创建进程(通过 fork()，实际上最终是 clone())，如何把新的执行镜像装入到地址空间 (通过 exec() 系统调用族)，如何表示进程的层次关系，父进程又是如何收集其后代的信息(通过 wait() 系统调用族)，以及进程最终如何消亡 (强制或者自愿地调用exit())。进程是一个非常基础、非常关键的抽象概念，位于每一种现代操作系统的核心位置，也是我们拥有操作系统(用来运行程序)的最终原因。

进程调度

上边讲到的进程，他在操作系统看来是程序的运行态表现形式。接下来讨论进程调度，它是确保进程能有效工作的一个内核子系统。

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序(常常简称调度程序)可看做在可运行态进程之间分配有限的处理器事件资源 的内核子系统。调度程序是像Linux这样的多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度地发挥作用，多进程才会有并发执行的效果。

调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，只要有可以执行的进程，那么就总会有进程正在执行。但是只要系统中可运行的进程数目比处理器 的个数多，就注定某一个给定时刻会有一些进程不能执行。这些进程在等待运行。在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。

多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统，但是这些进程并不都处于运行状态。

多任务系统可以分为两类：非抢占式多任务 和 抢占式多任务。像所有 Unix 的变体和许多其它现代操作系统一样，Linux提供了抢占式的多任务模式。 在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其它进程能够得到执行机会。这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间 是预先设置好的，而且有一个专门的名字，叫做进程的时间片。时间片实际上就是分配给每个可运行进程的处理器时间段。有效管理时间片能使调度程序从系统全局的 角度作出调度决定，这样做还可以避免个别进程独占系统资源。当今众多现代操作系统对程序运行都采用了动态时间片计算的方式，并且引入了可配置的计算策略。不过我们 将看到，Linux独一无二的“公平”调度程序本身并没有采取时间片来达到公平调度。

相反，在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步。理想情况下，进程通常作出让步，以便让每个可运行进程享有足够的处理器时间。但这种机制有很多缺陷： 调度程序无法对每个进程该执行多长时间作出统一规定，所以进程独占的处理器时间可能超出用户的预料；更糟的是，一个决不做出让步的悬挂进程就能使系统崩溃。 Unix从一开始采用的就是抢先式的多任务，Mac OS 9(以及其前身)、Windows3.1(以及其前身)这些不是。

Linux的进程调度

从 1991 年 Linux 的第一版到后来的 2.4 内核系列，Linux 的调度程序都相当简陋，设计近乎原始。当然它容易理解，但是它在众多可运行进程或者多处理器的环境下都 难以胜任。

正因为如此，在 Linux2.5 开发系列的内核中，调度程序做了大手术。开始采用一种叫做 O(1) 调度程序的新调度程序 —— 它是因为其算法的行为而得名。它解决了先前版本 Linux 调度程序的许多不足，引入了许多强大的新特性和性能特征。这里主要要感谢静态时间片算法和针对每一处理器的运行队列，它们帮助我们摆脱了先前调度程序设计上的限制。

O(1)调度器虽然在拥有数以十计(不是数以百计)的多处理器环境下尚能表现出近乎完美的性能和可扩展性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却 有一些先天不足。这些程序我们称其为交互进程 —— 它无疑包括了所有需要用户交互的程序。正因为如此，O(1)调度程序虽然对于大服务器的工作负载很理想，但是在有 很多交互程序要运行的桌面系统上则表现不佳，因为其缺少交互进程。自 2.6 内核系统开发初期，开发人员为了提高对交互程序的调度性能引入了新的进程调度算法。 其中最为著名的是**“反转楼梯最后期限调度算法(RSDL)”**，该算法吸取了队列理论，将公平调度的概念引入了Linux调度程序。并且最终在 2.6.23 内核版本中替代了 O(1) 调度算法，它此刻被称为 “完全公平调度算法”，简称 CFS。

接下来讲解调度程序设计的基础和完全公平调度程序如何运用、如何设计、如何实现以及与它相关的系统调用。我们当然也会讲解O(1)调度程序，因为它毕竟是 经典Unix调度程序模型的实现方式。

策略

策略决定调度程序在何时让什么进程运行。调度器的策略往往就决定系统的整体印象，并且，还要负责优化使用处理器时间。无论从哪个方面来看，它都是至关重要的。

I/O消耗型和处理器消耗型的进程

进程可被分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交 I/O 请求或是等待 I/O 请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为 它在等待更多的I/O请求时候最后总会阻塞(这里所说的I/O是指任何类型的可阻塞资源，比如键盘输入，或者是网络I/O)。举例来说，多数用户图形界面程序(GUI) 都属于I/O密集型，即便它们从不读取或者写入磁盘，它们也会在多数时间里都在等待来自鼠标或者键盘的用户交互操作。

相反，处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停的运行，因为它们没有太多的I/O需求。但是，因为它们不属于 I/O驱动型，所以从系统响应速度考虑，调度器不应该经常让它们运行。对于这类处理器消耗型的进程，调度策略往往是尽量降低它们的调度频率，而延长其运行时间。处理器消耗型进程的 极端例子就是无线循环地执行。更具代表性的例子就是那些执行大量数学计算的程序，如 sshkeygen 或者 MATLAB。

当然，这种划分方法并非是绝对的。进程可以同时展示这两种行为：比如，X Window 服务器既是 I/O 消耗型，也是处理器消耗型。 还有些进程可以是I/O消耗型，但不属于处理器消耗型活动范围。其典型例子就是字处理器，其通常以等待键盘输入。但在任一时刻可能又粘住处理器疯狂地进行 拼写检查或者宏计算。

调度撤略通常需要在两个矛盾的目标中寻找平衡：进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)。为了满足上述需求，调度程序通常采用一套非常复杂的 算法来决定最值得运行的进程投入运行，但是它往往并不保证低优先级进程会被公平对待。Unix系统的调度程序更倾向于 I/O 消耗型程序，以便提供更好的程序 响应速度。Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化(缩短响应时间)，更倾向于有限调度I/O消耗型进程。虽然如此，但在下面你会看到， 调度程序也并未忽略处理器消耗型的进程。

进程优先级

调度算法中最基本的一类就是基于优先级的调度。这时一种根据进程的价值和其对处理器时间的需求来对进程分级的想法，通常做法是(其并未被Linux系统完全采用) 优先级高的进程先运行，低的后运行，相同优先级的进程按轮询的方式进行调度(一个接一个，重复进行)。在某些系统中，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。

Linux采用了两种不同的优先级范围。第一种是 nice值，它的范围是从 -20 到 +19，默认值为0；越大的nice值意味着更低的优先级(nice意味着你对其它系统中的进程更"优待"")。 相比高 nice 值的进程，低 nice 值的进程可以获得更多的处理器时间。nice 值是所有 Unix 系统中的标准化概念——但不同的 Unix 系统由于调度算法不同，因此 nice 值的运用方式有所差异。比如一些基于Unix的操作系统， 如 Mac OS X，进程的 nice 值代表分配给进程的时间片的绝对值；而 Linux 系统中，nice 值则代表了时间片的比例。

第二种范围是实时优先级，其值的可配置的，默认情况下它的变化范围是 0 到 99(包括 0 和 99).与 nice 值意义相反，越高的实时优先级数值意味着进程优先级越高。 任何实时进程的优先级都高于普通进程，也就是说实时优先级和nice优先级处于互补相交的两个范畴。Linux 实时优先级的实现参考了 Unix 相关标准 —— 特别是 POSIX.1b。 大部分现代的 Unix 操作系统也都提供类似的机制。你可以通过命令：

1

ps -eo state,uid,pid,ppid,rtprio,time,comm

查看你系统中的进程列表，以及它们对应的实时优先级(位于RTPRIO列下)，其中如果有进程对应列显示 “-”，则说明它不是实时进程。

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间偏，但这并不是件简单的事情。时间片过长会导致系统对交互的 响应表现欠佳，让人觉得系统无法并发执行应用程序；时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。此外，I/O 消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来；I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好(比如这样可以让它们的高速缓存命中率更高)。

从上面的争论中可以看出，任何长时间片都将导致系统交互表现欠佳。很多操作系统中都特别重视这一点，所以默认的时间片很短，如 10ms。但是 Linux 的 CFS 调度器并没有直接分配时间片到进程，它是将处理器的使用比例划分给了进程。这样一来，进程所获的的处理器时间其实是和系统负载密切相关的。 这个比例进一步还会受进程 nice 值的影响， nice 值作为权重将调整进程所使用的处理器时间使用比。具有更高 nice 值(更低优先权) 的进程将被赋予低权重，从而 丧失了一小部分的处理器使用比；而具有更小nice值(更高优先级)的进程则会被赋予高权重，从而抢得更多的处理器使用比。

像前面所说的，Linux系统是抢占式的。当一个进程进入可运行态，他就被准许投入运行。在多数操作系统中，是否要将一个进程立刻投入运行(也就是抢占当前进程)， 是完全由进程优先级和是否有时间片决定的。而在 Linux 中使用新的 CFS 调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新 进程立刻投入运行，抢占当前进程。肉则，将推迟其运行。

调度策略的活动

想象下面这样一个系统，它拥有两个可运行的进程：一个文字编辑程序和一个视频编码程序。文字编辑程序很明显是 I/O 消耗型的，因为大多数时间都在等待用户的键盘输入 (无论用户的输入速度有多快，都不可能赶上处理的速度)。用户总是希望按下键系统能马上响应。

相反，视频编码程序是处理器消耗型的。除了最开始从磁盘上读出原始数据流和最后把处理好的视频输出外，程序所有的时间都用来对原始数据进行视频编码，处理器 很轻易地被 100% 使用。它对什么时间开始运行并没有太严格的要求 —— 用户几乎分辨不出也并不关心它到底是立刻就运行还是半秒钟以后才开始的。当然，它完成的越早越好，至于所花时间并不是我们关注的主要问题。

在这样的场景中，理想情况是调度器应该给予文本编辑器程序相比视频编码程序更多的处理器时间，因为它属于交互式应用。对于文本编辑器而言，我们有两个目标。第一是希望系统给它更多的处理器时间，这并非因为它需要更多的处理器时间 (其实它并不需要)，是因为我们我们希望在它需要时总能得到处理器；第二是我们希望文本编辑器能在其被唤醒时候(也就是当用户打字时候)抢占视频解码程序。 这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入。

在多数操作系统中，上述目标达成是要依赖系统分配给文本编辑器比视频解码程序更高的优先级和更多的时间片，先进的操作系统可以自动发现文本编辑器是交互型程序， 从而自动地完成上述分配动作。

Linux操作系统同样需要追求上述目标，但是它采用不同的方法。它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。加入文本编辑器和视频编码程序是仅有的两个运行程序，并且又具有同样的 nice 值， 那么处理器的使用比将都是 50% —— 它们平分了处理器时间。但是因为文本编辑器将更多的时间用于等待用户输入，因此它肯定不会用到处理器的 50%。同时， 视频解码程序无疑将能有机会用到超过 50% 的处理器时间，以便它能更快速的完成解码任务。

这里关键的问题是，当文本编辑器程序被唤醒的时候将会发生什么。我们首先目标是确保其能在用户输入发生时候立刻运行。在上述场景中，一旦文本编辑器被唤醒， CFS发现文本编辑器比视频解码器运行的时间短的多。这种情况下，为了兑现让所有进程都能公平分享处理器的承诺，它会立即抢占视频解码程序，让文本编辑器 投入运行。文本编辑器运行后，立即处理了用户的击键输入后，又一次进入睡眠等待用户下一次输入。因为文本编辑器并没消费掉承诺给它的50%处理器使用比，因此情况依旧，CFS总会毫不犹豫的让文本编辑器在需要时候被投入运行，而让视频处理程序 只能在剩余下的时刻运行。

Linux 调度算法

在前面内容中，我们抽象地讨论了进程调度原理，只是偶尔提及 Linux 如何把给定的理论应用到实际中。在已有的调度原理基础上，我们进一步探讨具有Linux特色的进程调度程序。

调度器类

Linux 调度器是以模块方式提供的，这样做的目的是运行不同类型的进程可以又针对性的选择调度算法。

这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在 kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

完全公平调度(CFS)是一个针对普通进程的调度类，在 Linux 中称为 SCHED_NORMAL (在 POSIX 中称为 SCHED_OTHER)，CFS 算法实现定义在文件 kernel/sched_fair.c 中。本节下面的内容将重点介绍 CFS 算法。

Unix系统中的进程调度

在讨论公平调度算法前，我们必须首先认识一下传统 Unix 系统的调度过程。正如前面所述，现代进程调度器有两个通用的概念：进程优先级和时间片。时间片是指进程运行多少时间， 进程一旦启动就会有一个默认时间片。具有更高优先级的进程将运行的更频繁，而且(在多数系统上)也会被赋予更多的时间片。在 Unix 系统上，优先级以 nice 值形式 输出给用户空间。这点听起来简单，但是在现实中，却会导致许多反常的问题，我们下面具体讨论。

第一个问题，若要将 nice 值映射到时间片，就必然需要将 nice 单位值对应到处理器的绝对时间。但这样做将导致进程切换无法最优化进行。举例说明， 假定我们将默认 nice 值(0) 分配给一个进程 —— 对应的是一个 100ms 的时间片：同时再分配一个最高 nice 值(+20，最低的优先级)给另一个进程 —— 对应的时间片是 5ms。我们接着假定上述两个进程都处于可运行状态。那么默认优先级的进程将获得 20/21 (105ms中的100ms) 的处理器时间，而低优先级的进程会获得 1/21(105ms中的5ms)的处理器时间。我们可以选择任意数值用于本例子中。现在，我们看看如果运行两个同等低优先级的进程的情况将如何。我们是希望它们能各自获得 一半的处理器时间，事实上也确实如此。但是另一个进程每次只能获得 5ms 的处理器时间(10ms中各占一般)。也就是说，相比刚才例子中 105ms 内进行一次上下文切换，现在则需要在 10ms 内继续进行两次上下文切换。类推，如果是两个具有普通优先级的进程，它们同样会每个获得 50% 的处理器时间，但是是在 100ms 内各获得一般。显然，我们看到这些时间片的分配方式并不很理想：它们是给定 nice 值到时间片映射与进程运行优先级混合的共同作用结果。事实上，给定高 nice 值(低优先级)的进程往往是后台进程，且多是计算密集型；而普通优先级的进程则更多的是前台用户任务。所以这种时间片分配方式显然是和初衷背道而驰的。

第二个问题 设计相对 nice 值，同时和前面的 nice 值到时间片映射关系也脱不了关系。假设我们有两个进程，分别具有不同的优先级。第一个假设 nice 值只是0， 第二个假设是1。它们将被分别映射到时间片 100ms 和 95ms (O(1)调度算法确实就这么干类)。它们的时间片几乎一样，差别微乎其微。但是如果我们的进程分别赋予 18 和 19 的 nice 值，那么它们则分别被映射为 10ms 和 5ms 的时间片。如果这样，前者相比后者获得了两倍的处理器时间！不过 nice 值通常都使用相对值(nice系统调用是在原值上 增加或减少，而不是在绝对值上操作)，也就是说：“把进程的nice值减少1”所带来的效果极大的取决于其 nice 的初始值。

第三个问题 如果执行 nice 值到时间片的映射，我们需要能分配一个绝对时间片，而且这个绝对时间片必须能在内核的测试范围内。在多数操作系统中，上述要求意味着时间片必须是 定时器节拍的整数倍。但是这么做必然会引发了几个问题。首先，最小时间片必然是定时器节拍的整数倍，也就是 10ms 或者 1ms 的倍数。

其次，系统定时器限制了两个时间片的差异：连续的 nice 值映射到时间片，其差别范围多至 10ms 或者 少则 1ms。最后，时间偏还会随着定时器节拍改变。

第四个问题 也是最后一个关于基于优先级的调度器为了优化交互任务而唤醒相关进程的问题。这种系统中，你可能为了进程能更快的投入运行，而去对新要唤醒的进程提升优先级，即便它们的 时间片已经用尽了。虽然上述方法确实能提升不少交互性能，但是一些例外情况也有可能发生，因为它同时也给某些特殊的睡眠/唤醒用例一个玩弄调度器的后门， 使得给定进程打破公平原则，获得更多处理器时间，顺还系统中其它进程的利益。

上述问题中的绝大多数都可以通过对传统 Unix 调度器进行改造解决，虽然这种改造修改不小，但是也并非是结构性的调整。比如，将 nice 值呈几何增加而非算数增加 的方式解决第二个问题：采用一个新的度量机制将从 nice 值到时间片的映射与定时器节拍分离开来，一次解决第三个问题。但是这些解决方案都回避了实质问题 —— 即 分配绝对的时间片引发的固定的切换频率，给公平性造成了很大变数。CFS采用的方法是对时间片分配方式进行根本性的重新设计(就进程调度器而言)：完全摒弃时间片 而是分配给进程一个处理器使用比重。这种方式下，CFS 确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。

公平调度

CFS 的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程将获得 $1/n$ 的处理器时间 —— n 是指可运行进程的数量。 同时，我们可以调度给它们无限小的时间周期，所以在任何可测量周期内，我们给予 n 和进程中每个进程同样多的运行时间。距离说明，加入我们有两个运行进程，在标准 Unix 调度模型中，我们先运行其中一个 5ms，然后再运行另一个 5ms。但它们任何一个运行时候都将占有 100% 的处理器，它们各自使用处理器一半的能力。

当然，上述理想模型并非显示，因为我们无法在一个处理器上真的同时运行多个进程。而且如果每个进程运行无限小的时间周期也是不高效的 —— 因为调度时进程抢占会带来一定的 代价：将一个进程换出，另一个换入本身有消耗，同时还会影响到缓存的效率。因此虽然我们希望所有进程能值运行一个非常短的周期，但是 CFS 充分考虑了这将带来的额外消耗，现实中首先要 确保系统新能不受损失。CFS的做法是允许每一个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，

CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice 值来计算时间片。nice值在 CFS 中被作为进程获得的处理器运行比的权重，这是相对默认 nice 值 进程的进程而言的；相反，更低的 nice 值(越高的优先级)的进程获得更好的处理器使用权重。

每个进程都按其权重在全部可运行进程中所占的 “时间片” 来运行，为了计算准确的时间片，CFS 为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标称作 “目标延迟”， 越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统总吞吐能力。让我们假定目标延迟值是 20ms，我们有两个同样优先级 的可运行任务(无论这些任务的优先级是多少)。每个任务在被其它任务抢占前运行 10ms，如果我们有 4 个这样的任务，则每个智能运行 5ms。进一步设想， 如果有 20 个这样的任务，那么每个仅仅只能获得 1ms 的运行时间。

你一定注意到了，当可运行任务数量趋于无限时候，它们各自获得的处理器时间比和时间片都将趋于0.这样无疑造成了不可接收的切换消耗。CFS 为此引入每个进程获得的 时间片底线，这个底线称为最小粒度。默认情况下这个值是 1ms。如此依赖，即便是可运行进程数量趋于无穷，每个最少也能获得 1ms 的运行时间，确保切换消耗被限制在一定 范围内(敏锐的读者会注意到假如在进程数量变得非常多的情况下，CFS并非一个完美的公平制度，因为这时处理器时间片再小也无法突破最小粒度。的却如此， 尽管修改过的公平队列方法确实能提高这方面的公平性，但是 CFS 的算法本身其实已经决定在这方面折中了。但还好，因为通常情况下系统中只会有几百个可运行进程，无疑， 这时 CFS 的相当公平的)。

现在，让我们再看看具有不同 nice 值的两个可运行进程的运行情况 —— 比如一个具有默认 nice 值(0)，另一个具有额 nice 值为 5.这些不同的 nice 值对应不同的权重， 所以上述两个进程将获得不同的处理器使用比。这个例子中，nice 值是 5 的进程的权重是默认 nice 进程的 1/3.如果我们的目标延迟是 20ms，那么这两个进程将分别获得 15ms 和 5ms 的 处理器时间。再比如我们的两个可运行进程的 nice 值分别是 10 和 15，它们分配的时间片将是多少呢？还是 15ms 和 5ms！可见，绝对的 nice 值不再影响调度决策：只有相对值才会影响处理器时间的分配比例。

总结以下，任何进程所获得的处理器时间是由它自己和其它所有可运行进程 nice 值的相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。 CFS 称为公平调度器是因为它确保给每个进程公平的处理器使用比。正如我们知道的，CFS 不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下，降低了调度延迟带来的不公平性。

Linux 调度的实现

在讨论了采用 CFS 调度算法的动机和其内部逻辑后，我们现在可以开始具体探索 CFS 是如何得以实现的。其相关代码位于文件 kernel/sched_fair.c 中。我们将特别关注其四个组成部分：

• 时间记账
• 进程选择
• 调度器入口
• 睡眠和唤醒

时间记账

所有的调度器都必须对进程运行时间做记账。多数 Unix 系统，正如我们前面所说，分配一个时间片给每一个进程。那么每次系统时钟节拍发生时候，时间片都被减少一个节拍周期。 当一个进程的时间片被减少到0时候，它就会被另一个尚未减到 0 的时间片可运行进程抢占。

调度器实体结构

CSF 不再有时间片的概念，但是它也必须维护每个进程运行的时间记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。CFS使用调度器实体结构 (定义在文件<linux/sched.h>的 struct_sched_entity 中)来追踪进程运行记账：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

struct sched_entity {
    struct load_weight              load;
    struct rb_node                  run_node;
    struct list_head                group_node;
    unsigned int                    on_rq;
    u64                             exec_start;
    u64                             sum_exec_runntime;
    u64                             vruntime;
    u64                             prev_sum_exec_runtime;
    u64                             last_wakeup;
    u64                             avg_overlap;
    u64                             nr_migrations;
    u64                             start_runtime;
    u64                             avg_wakeup;
    
    // 这里省略了很多统计变量，只有在设置了 CONFIG_SCHEDSTATS 时候才启用这些变量
};

调度器实体结构作为一个名为 se 的成员变量，嵌入在进程描述符 struct task_struct 内。

虚拟实时

vruntime 变量存放进程的虚拟运行时间，该运行时间(华仔运行上的时间和)的计算是经过了所有可运行进程总数的标准化(或者说是被加权的)。虚拟时间是以 ns 为单位的， 所以 vruntime 和定时器节拍不再相关。虚拟运行时间可以帮助我们逼近 CFS 模型所追求的 “理想多任务处理器”。如果我们真有这样一个理想的处理器，那么我们就不再需要 vruntime 了。因为优先级相同的所有进程的虚拟运行时间都是相同的 —— 所有任务都被接收到相等的处理器份额。但是因为处理器无法实现完美的多任务，它必须依次运行每个任务。 因此 CFS 使用 vruntime 变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

定义在 kernel/sched_fair.c 文件中的 update_curr() 函数实现了该记账功能：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static void update_curr (struct cfs_rq* cfs_rq)
{
    struct sched_entity* curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock;
    unsigned long delta_exec;

    if (unlikely(!curr)) {
        return;
    }

    // 获得从最后依次修改负载后当前任务所占用的运行总时间(在 32 位系统上这不会溢出)
    delta_exec = (unsigned long) (now - curr->exec_start);
    if (!delta_exec)
        return;
    __update_curr(cfs_rq, curr, delta_exec);
    curr->exec_start = now;

    if (entity_is_task(curr)) {
        struct task_struct* curtask = task_of (curr);
        trace_shced_stat_runtime(curtask, delta_exec, curr->vruntime);
        cpuacct_charge(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }
}

update_curr() 计算了当前进程的执行时间，并且将其存放在变量 delta_exec 中。然后它又将运行时间传递给了 __update_curr()，由后者再根据当前可运行进程总数对运行时间进行加权计算。 最终将上述的权重值与当前运行进程的 vrunntime 相加。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 更新当前任务的运行时统计数据。跳过不在调度类中的当前任务
static inline void __update_curr (struct cfs_rq* cfs_rq, struct shced_entity* curr, unsigned long delta_Exec)
{
    unsigned long delta_exec_weighted;
    schedstat_set (curr->exec_max, max((u64)delta_exec,curr->exec_max));

    curr->sum_exec_runtime += delta_exec;
    schedstat_add (cfs_rq, exec_clock, delta_Exec);
    delta_exec_weighted = calc_delta_fair (delta_exec, curr);

    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

update_curr()是由系统定时器周期性调用，无论在进程处于可运行状态，还是被阻塞处于不可运行状态。根据这种方式，vruntime 可以准确地测量给定进程的运行时间， 而且可直到谁应该是下一个被运行的进程。

进程选择

在前面内容中我们的讨论中谈到若存在一个完美的多任务处理器。所有可运行进程的 vruntime 值将一致。但事实上我们没有找到完美的多任务处理器，因此 CFS 试图利用一个简单的 规则去均衡进程的虚拟运行时间：当 CFS 需要选择下一个运行时间时候，它会挑一个具有最小 vruntime 的进程。这其实就是 CFS 调度算法的核心：选择具有最小 vruntime 的任务。 那么剩下的内容我们就来讨论到底是如何实现选择具有最小 vruntime 值的进程。

CFS 使用红黑树来组织可运行进程队列，并利用其迅速找到最小 vruntime 值的进程

在 linux 中，红黑树被称为 btree，它是一个自平衡二叉搜索树。

挑选下一个任务

我们先假设，有那么一个红黑树存储了系统中所有的可运行进程，其中节点的键值便是可运行进程的虚拟运行时间。稍后我们将看到如何生成该树，但现在我们假定已经拥有它来。CFS 调度器选取待运行的下一个进程， 是所有进程中 vruntime 最小的哪个，它对应的便是在树中最左侧的叶子节点。实现这一过程的函数是：__pick_next_entity()，它定义在文件 kernel/sched_fair.c 中：

1
2
3
4
5
6
7
8
9

static struct sched_entity* __pick_next_entity(struct cfs* cfs_rq)
{
    struct rb_node* left = cfs_rq->rb_leftmost;
    
    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

注意 __pick_next_entity() 函数本身并不会遍历树找到最左叶子节点，因为该值已经缓存在 rb_leftmost 字段中。虽然红黑树让我们可以很有效地找到最左叶子节点(O(树的高度))等于 树节点总数的 O(log n)，这是平衡树的优势)，但是更容易的做法是把最左叶子节点缓存起来。这个函数的返回值便是 CFS 调度选择的下一个运行进程。如果该函数返回值是 NULL， 那么表示没有最 左叶子节点，那就是说树中没有任何节点了。这种情况下，表示没有可运行进程， CFS 调度器便选择 idle 任务运行。

向树中加入进程

现在，我们来看 CFS 如何将进程加入 rbtree 中，以及如何缓存最左叶子节点。这一切发生在进程变为可运行状态(被唤醒)或者是通过fork()调用第一次创建进程时。enqueue_entity()函数实现了这一目的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

static void enqueue_entity (struct cfs_rq* cfs_rq, struct sched_entity* se, int flags)
{
    // 通过调用 update_curr()，在更新 min_vruntime 之前先更新规范化的 vruntime
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
        se->vruntime += cfs_rq->min_vruntime;

    // 更新 当前任务 的运行时统计数据
    update_curr(cfs_rq);

    account_entity_enqueue(cfs_rq, se);

    if (flags & ENQUEUE_WAKEUP) {
        place_entity(cfs_rq, se, 0);
        enqueue_sleeper(cfs_rq, se);
    }

    update_stats_enqueue(cfs_rq, se);
    check_spread(cfs_rq, se);
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
}

该函数更新运行时间和其它一些统计数据，然后调用 __enqueue_entity() 进行繁重的插入操作，把数据项真正插入到红黑树中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 把一个调度实体插入 红黑树中

static void __enqueue_entity (struct cfs_rq* cfs_rq, struct sched_entity* se)
{
    struct rb_node** link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node* parent = NULL;
    struct sched_entity* entity;
    
    s64 key = entity_key(cfs_rq, se);
    int leftmost = 1;

    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        // 我们并不关心冲突，具有相同键值的节点呆在一起
        if (key < entity_key(cfs_rq, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    // 维护一个缓冲，其中存放树最左叶子节点(也就是最长使用的)
    if (leftmost) {
        cfs_rq->rb_leftmost = &se->run_node;
    }
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

我们来看看上述函数，while()循环中遍历树以寻找合适的匹配键值，该值就是被插入进程的 vruntime。平衡二叉树的基本规则是，如果键值小于当前节点的键值，则需转向树的左分支；相反如果大于当前节点的键值，则需转向右分支。 如果一旦走过右边分支，哪怕一次，也说明插入的进程不会是新的最左节点，因此可以设置 leftmost 为 0.如果一致都是向左移动，那么 leftmost 维持 1，这说明 我们有一个新的最左节点，并且可以更新缓存 —— 设置 rb_leftmost 指向被插入的进程。当我们沿着一个方向和一个没有自节点的节点比较后：link如果这时是 NULL，循环随之终止。当退出循环后，接着在父节点上调用 rb_link_node()， 以使得新插入的进程成为其子节点。最后函数 rb_insert_color() 更新树的自平衡相关的属性。

从树中删除进程

最后我们看看 CFS 是如何从红黑树中删除进程的。删除动作发生在进程堵塞(变为不可运行态)或者终止时(结束运行)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

static void dequeue_entity (struct cfs_rq* cfs_rq, struct sched)entity* se, int sleep)
{
    // 更新 “当前任务” 的运行时统计数据
    update_curr(cfs_rq);

    update_stats_dequeue(cfs_rq, se);
    clear_buddies(cfs_rq, se);

    if (se != cfs_rq->curr)
        __dqueue_entity (cfs_rq, se);

    update_min_vruntime(cfs_rq);

    // 在更新 min_vruntime 之后对调度实体进行规范化，因为更新可以指向 "->curr" 项，我们需要在规范化的位置反映这一变化
    if (!sleep)
        se->vruntime -= cfs_rq->min_vruntime;
}

和给红黑树添加进程一样，实际工作是由辅助函数 __dequeue_entity() 完成的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static void __dequeue_entity(struct cfs_rq* cfs_rq, struct sched_entity* se)
{
    if (cfs_rq->rb_leftmost == &se->run_node) {
        struct rb_node* next_node;
        next_node = rb_next(&se->run_node);
        cfs_rq->rb_leftmost = next_node;
    }

    rb_erase(&se->run_node, &cfs_rq->task_timeline);
}

从红黑树中删除进程要容易得多，因为 rbtree 实现了 rb_erase() 函数，它可完成所有工作。该函数的剩下工作是更新 rb_leftmost 缓存。如果要删除的进程是最左节点，那么该 函数要调用 rb_next() 按顺序遍历，找到谁是下一个节点，也就是当前最左节点被删除后，新的最左节点。

调度器入口

进程调度的主要入口点是函数 schedule()，它定义在文件 kernel/sched.c 中。它正是内核其它部分用于调度进程调度器的入口：选择哪个进程可以运行，合适将其投入运行。 Schedule() 通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类 —— 后者需要由自己的可运行队列，然后问后者谁才是下一个该运行的进程。 知道了这个背景就不会吃惊 schedule() 函数为何实现得如此简单。该函数中唯一重要的事情是，它会调用 pick_next_task()(也定义在文件 kernel/sched.c中)。 pick_next_task() 会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 挑选最高优先级的任务
static inline struct task_struct* pick_next_task (struct rq* rq)
{
    const struct sched_class* class;
    struct task_struct* p;

    // 优化：我们知道如果所有任务都在公平类中，那么我们就可以直接调用哪个函数
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))  {
            return p;
        }
    }

    class = sched_class_highest;
    for (;;) {
        p = class->pick_next_task(req);
        if (p)
            return p;
        // 永不会 NULL，因为 idle 类总会返回非 NULL 的 p 
        class = class->next;
    }
}

注意该函数开始部分的优化。因为 CFS 是普通进程的调度类，而系统运行的绝大多数进程都是普通进程，因此这里有一个小技巧用来加速选择下一个 CFS 提供的进程， 前提是所有可运行进程数量等于 CFS 类对应的可运行进程数(这样就说明所有的可运行进程就是 CFS 类的)。

该函数的核心是 for() 循环，它以优先级为序，从最高的优先级类开始，遍历了每一个调度类。每一个调度类都实现了 pick_next_task() 函数，它会 返回指向下一个可运行进程的指针，或者没有时返回 NULL。我们会从第一个返回非 NULL 值的类中选择下一个可运行进程。 CFS 中 pick_next_task() 实现会调用 pick_next_entity()，而该函数会再来调用我们前面内容中讨论过的 __pick_next_entity() 函数。

睡眠和唤醒

休眠(被阻塞) 的进程处于一个特殊的不可执行状态。这点非常重要，如果没有这种特殊状态的话，调度器程序就可能选出一个本不愿意被执行的进程，更糟糕的是， 休眠就必须以轮询的方式实现了。进程休眠由多种原因，但肯定都是为了等待一些事件。事件可能是一段时间从文件 I/O 读更多数据，或者是某个硬件事件。

一个进程还有可能在尝试获取一个已被占用的内核信号量时被迫进入休眠。休眠的一个常见原因就是文件 I/O —— 如进程对一个文件执行了 read() 操作， 而这需要从磁盘里读取。还有，进程在获取键盘输入的时候也许要等待。无论哪种情况，内核的操作都相同：进程把自己标记成休眠状态，从可执行红黑树中移出，放入 等待队列，然后调用 schedule() 选择和执行一个其它进程。唤醒的过程刚高相反：进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

之前讨论过，休眠有两种相关的进程状态：TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE。它们的唯一区别是处于 TASK_UNINTERRUPTIBLE 的进程 会忽略信号，而处于 TASK_INTERRUPTIBLE状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上，等待某些事件，不能够运行。

1. 等待队列

休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用 wake_queue_head_t 来代表等待队列。等待队列可以通过 DECLARE_WAITQUEUE() 静态创建，也可以由 init_waitqueue_head() 动态创建。进程把自己放入等待队列中并设置成不可执行状态。当与等待队列相关的事件发生的时候，队列上的进程会被唤醒。 为了避免产生竞争条件，休眠和唤醒的实现不能有纰漏。

针对休眠，以前曾经使用过一些简单的接口。但那些接口会带来竞争条件：有可能导致在判定条件变为真后，进程却开始了休眠，那样就会使进程无限期的休眠下去。所以，在内核中进行休眠的推荐操作就相对复杂了一些：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 'q' 是我们希望休眠的等待队列
DEFINE_WAIT(wait);

add_wait_queue(q, &wait);
while(!condition) {
    // condition 是我们在等待的事件
    prepare_to_Wait(&q, &wait, TASK_INTERRUPTIBLE);
    if (signal_pending(current)) 
        // 处理信号
    schedule();
}

finish_Wait (&q, &wait);

进程通过执行下面几个步骤将自己加入到一个等待队列中：

1. 调用宏 DEFINE_WAIT() 创建一个等待队列的项。
2. 调用宏 add_wait_queue() 把自己加入到队列中。该队列会在进程等待的条件满足时候唤醒它。当然我们必须在其它地方撰写相关代码，在事件发生时候，对等待队列执行 wake_up() 操作。
3. 调用 prepare_to_wait() 方法将进程的状态变为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列，这时在接下来的循环遍历中所需的
4. 如果状态被设置为 TASK_INTERRUPTIBLE，则信号唤醒进程。这就是所谓的伪唤醒(唤醒不是因为事件的发生)，因此检查并处理信号。
5. 当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它会退出循环；如果不是，它再次调用 schedule() 并一直重复这步操作。
6. 当条件满足后，进程将自己设置为 TASK_RUNNING 并调用 finish_wait() 方法把自己移出等待队列。

如果在进程开始休眠之前条件就已经达成了，那么循环会退出，进程不会存在错误地进入休眠的倾向。需要注意的是，内核代码在循环体内常常需要完成一些其它任务，比如，它可能在调用 schedule() 之前需要 释放掉锁，而在这以后再重新获取它们，或者响应其它事件。

函数 inotify_read()，位于文件 fs/notify/inotify/inotify_user.c 中，负责从通知文件描述符中读取信息，它的实现无疑是等待队列的一个典型用法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

static ssize_t inotify_read (struct file* file, char __user* buf, size_t count, loff_t* pos)
{
    struct fsnotify_group* group;
    struct fsnotify_event* kevent;
    char __user* start;
    int    ret;
    DEFINE_WAIT(wait);

    start = buf;
    group = file->private_data;
    
    while (1) {
        prepare_to_wait(&group->notification_waitq, &wait, TASK_INTERRUPTIBLE);
        mutex_lock(&group->notification_mutex);
        kevent = get_one_event(group, count);
        mutex_unlock (&group->notification_mutex);

        if (kevent) {
            ret = PTR_ERR(kevent);
            if (IS_ERR(kevnet))
                break;

            ret = copy_event_to_user(group, kevent, buf);
            fsnotify_put_event(kevent);
            if (ret < 0) {
                break;
            }
            buf += ret;
            count -= ret;
            continue;
        }
        ret = -EAGAIN;
        if (file->f_flags & O_NONBLOCK) {
            break;
        }
        ret = - EINTR;
        if (signal_pending(current)) {
            break;
        }
        if (start != buf) {
            break;
        }
        schedule();
    }
    finish_wait (&group->notification_waitq, &wait);
    if (start != buf && ret != -EFAULT) {
        ret = buf - start;
    }

    return ret;
}

这个函数遵循了我们例子中的使用模式，主要的区别是它在 while 循环中检查了状态，而不是在 while 循环条件语句中。原因是该条件的检测更复杂一些，而且需要 获得锁。也正因为如此，循环退出是通过 break 完成的。

2. 唤醒

唤醒操作是通过函数 wake_up() 进行，它会唤醒指定的等待队列上的所有进程。它调用函数 tray_to_wake_up()，该函数负责将进程设置为 TASK_RUNNING状态，调用 enqueue_task() 将此进程放入红黑树中，如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置 need_resched标志。通常哪段代码促使等待条件达成，它就要负责随后调用 wake_up() 函数。举例来说，当磁盘数据到来时候，VFS就要负责对等待队列调用 wake_up()，以唤醒队列中等待这些数据的进程。

关于休眠有一点需要注意，存在虚假的唤醒。有时候进程被唤醒并不是因为它所等待的条件达成了才需要用一个循环处理来保证它等待的条件真正达成。

抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在 kernel/sched.c 中的 context_switch() 函数负责处理。每当一个新的进程被选出来准备投入运行的时候， schedule()就会调用该函数。它完成了两项基本的工作：

• 调用声明在 <asm/mmu_context.h> 中的 switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
• 调用声明在 <asm/system.h> 中的 switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其它任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。

内核必须知道在什么时候调用 schedule()。如果仅靠用户程序代码显式调用 schedule()，它们可能会永远地执行下去。相反，内核提供了一个 need_resched 标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时候，scheduler_tick() 就会设置这个标志：当一个优先级高的进程 进入可执行状态的时候，try_to_wake_up()也会设置这个标志，内核检查该标志，确认其被设置，调用 schedule() 来切换到一个新的进程。该标志对于 内核来讲是一个信息，它表示有其它进程应当被运行来，要尽快调用调度程序。

以下是用于访问和操作 need_resched 的函数

再返回用户空间以及从中断返回的时候，内核也会检查 need_resched 标志。如果已被设置，内核会在继续执行之前调用调度程序。

每个进程都包含一个 need_resched 标志，这时因为访问进程描述符内的数值要比访问一个全局变量快(因为 current 宏速度很快并且描述符通常都在 高速缓存中)。在 2.2 以前的内核版本中，该标志曾经是一个全局变量。 2.2 到 2.4 版内核中它在 task_struct 中。而在 2.6 版中，它被移到 thread_info 结构体中，用一个特别的标志变量中的一位来表示。

1. 用户抢占

内核即将返回用户空间的时候，如果 need_resched 标志被设置，会导致 schedule() 被调用，此时就会发生用户抢占。在内核返回用户空间的时候，它 知道自己是安全的，因为既然它可以继续去执行当前进程，那么它自然可以再去选择一个新的进程去执行。所以，内核无论是在中断处理程序还是在系统调用后返回， 都会检查 need_resched 标志。如果它被设置来，那么，内核会选择一个其它(更合适的)进程投入运行。从中断处理程序或系统调用返回的返回路径都是跟体系结构相关的 在 entry.S (此文件不仅包含内核入口部分的程序，内核退出部分的相关代码也在其中)文件中通过汇编语言来实现。

简而言之，用户抢占在以下情况时候产生：

• 从系统调用返回用户空间时候
• 从中断处理程序返回用户空间时候

2. 内核抢占

与其它大部分的 Unix 变体和其它大部分操作系统不同， Linux 完整地支持内核抢占。在不支持内核抢占的内核中，内核代码可以一直执行，到它完成为止。也就是说，调度程序没有办法在一个内核级 的任务正在执行的时候重新调度 —— 内核中的各任务是以协作方式调度的，不具备抢占性。内核代码一致要执行到完成(返回用户空间)或明显的阻塞为止。 在 2.6 版的内核中，内核引入来抢占能力。现在，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。

那么，什么时候重新调度才是安全的呢？只要没有持有锁，内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持 SMP 的，所以，如果没有持有锁， 正在执行的代码就是可重新导入的，也就是可以抢占的。

为了支持内核抢占所做的第一处变动，就是为每个进程的 thread_info 引入 preempt_count 计数器。该计数器初始值为0，每当使用锁的时候数值 加1，释放锁的时候数值减1.当数值为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查 need_resched 和 preempt_count 的 值。如果 need_resched 被设置，并且 preempt_count 为零的话，这说明有一个更为重要的任务需要执行并且可以安全的抢占，此时，调度程序就会被调用。 如果 need_resched 被设置，并且 preempt_count 为 0 的话，这说明有一个更为重要的任务需要执行并且可以安全的抢占，此时，调度程序就会被调用。 如果 preempt_count 不为0，说明当前任务持有锁，所以抢占是不安全的。这时，内核就会像通常那样直接从中断返回当前执行过程。如果当前进程持有的 所有的锁都被释放掉来，preempt_count都会重新为0.此时，释放锁的代码会检查 need_resched 是否被设置。如果是的话，就会调用调度程序。 有些内核代码需要允许或禁止内核抢占。

如果内核中的进程被阻塞了，或者它显式的调用了 schedule()，内核抢占也会显式地发生。这种形式的内核抢占从来都是受支持的，因为根本无须额外的逻辑来 保证内核可以安全地被抢占。如果代码显式的调用了 schedule()，那么它应该清除自己是可以安全地被抢占的。

内核抢占会发生在：

• 中断处理程序正在执行，且返回内核空间之前。
• 内核代码再一次具有可强占性的时候。
• 如果内核中的任务显式地调用 schedule()。
• 如果内核中的任务阻塞(这同样也会导致调用schedule())。

实时调度策略

Linux 提供了两种实时调度策略：SCHED_FIFO和SCHED_RR 。而普通的、非实时的调度策略是 SCHED_NORMAL。借助调度类的框架，这些实时策略并不被完全公平调度器来管理， 而是被一个特殊的实时调度器管理。具体实现定义在文件 kernel/sched_rt.c 中，在接下来的内容中我们将讨论实时调度策略和算法。

SCHED_FIFO实现了一种简单的、先入先出的调度算法：它不使用时间片。处于可运行状态的 SCHED_FIFO级的进程会比任何 SCHED_NORMAL 级的进程都先得到调度。一旦 一个 SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止：它不基于时间片，可以一直执行下去。只有更高优先级的 SCHED_FIFO或者SCHED_RR任务才能抢占 SCHED_FIFO 任务。如果有两个或者更多的同优先级的 SCHED_FIFO 级进程，它们会轮流执行，但是依然只有在它们愿意 让出处理器时候才会退出。只要有 SCHED_FIFO 级进程在执行，其它级别较低的进程就只能等待它变为不可运行态后才有机会执行。

SCHED_RR和SCHED_FIFO大体相同，只是 SCHED_RR 级的进程在耗尽实现分配给它的时间后就不能在继续执行了。也就是说， SCHED_RR是带有时间片的 SCHED_FIFO —— 这时一种实时轮流调度算法。当 SCHED_RR 任务耗尽它的时间片时，在同一优先级的其它实时进程被轮流调度。时间片只用来重新调度同一 优先级的进程。对于 SCHED_FIFO 进程，高优先级总是立即抢占低优先级，但低优先级决不能抢占 SCHED_RR 任务，即使它的时间片耗尽。

这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定优先级别的实时进程总能抢占优先级比它低的进程。

Linux 的实时调度算法提供了一种软实时工作方式。软实时的含义是，内核调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求。相反，硬实时系统保证在一定条件下， 可以满足任何调度的要求。Linux对于实时任务的调度不做任何保证。虽然不能保证硬实时工作方式，但 Linux 的实时调度算法的性能还是不错的。2.6版本的内核可以满足严格的时间要求。

实时优先级范围从 0 到 MAX_RT_PRIO 减1.默认情况下，MAX_RT_PRIO 为 100 —— 所以默认的实时优先级范围是从 0 到 99。SCHED_NORMAL 级进程的 nice 值共享了这个取值空间；它的取值范围是从 MAX_RT_PRIO 到(MAX_RT_PRIO + 40)。也就是说，在默认情况下，nice 值从 -20 到 +19直接对应的是从 100 到 139 的实时优先级范围。

与调度相关的系统调用

Linux 提供了一个系统调用族，用于管理与调度程序相关的参数。这些系统调用可以用来操作和处理进程优先级、调度策略以及处理器绑定，同时还提供了显式的将处理器交给其它进程的机制。

与调度有关的系统调用：

与调度策略和优先级相关的系统调用

sched_setscheduler() 和 sched_getscheduler() 分别用于设置和获取进程的调度策略和实时优先级。与其它的系统调用相似，它们的实现也是 由许多参数检查、初始化和清理构成的。其实最重要的工作在于读取或改写进程task_struct的policy和rt_priority的值。

sched_setparam()和sched_getparam()分别用于设置和获取进程的实时优先级。这两个系统调用获取封装在sched_param特殊结构体的 rt_priority中。sched_get_priority_max()和sched_get_priority_min()分别用于返回给定调度策略的最大和最小优先级。实时调度策略 的最大优先级是 MAX_USER_RT_PRIO 减1，最小优先级等于1.

对于一个普通的进程，nice()函数可以将给定进程的静态优先级增加一个给定的量。只有超级用户才能在调用它时候使用负值，从而提高进程的优先级。 nice()函数会调用内核的 set_user_nice()函数，这个函数会设置进程的 task_struct 的 static_prio 和 prio值。

与处理器绑定有关的系统调用

Linux 调度程序提供强制的处理器绑定机制。也就是说，虽然它尽力通过一种软的(或者说自然的)亲和性试图使进程尽量在同一个处理器上运行，但是它也 允许用户强制指定“这个进程无论如何都必须在这些处理器上运行”。这种强制的亲和性保存在进程 task_struct 的 cpus_allowed这个位掩码标志中。 该掩码标志的每一位对应一个系统可用的处理器。默认情况下，所有的位都被设置，进程可以在系统中所有可用的处理器上执行。用户可以通过 sched_setaffinity() 设置不同的一个或几个位组合的位掩码，而调用 sched_getaffinity() 则返回当前的 cpu_allowed 位掩码。

内核提供的强制处理器绑定的方法很简单。首先，当处理进行第一次创建时候，它继承了其父进程的相关掩码。由于父进程运行在指定处理器上，子进程也运行在 相应处理器上。最后，加载平衡器只把任务拉到允许的处理器上，因此，进程只运行在指定处理器上，对处理器的指定是由该进程描述符的cpus_allowed域设置的。

放弃处理器时间

Linux 通过 sched_yield() 系统调用，提供了一种让进程显式将处理器时间让给其它等待执行进程的机制。它是通过将进程从活动队列中(因为进程正在执行， 所以它肯定位于此队列当中)移到过期队列中实现的。有此产生的效果不仅抢占了该进程并将其放入优先级队列的最后面，还将其放入过期队列中——这样能确保在 一段时间内它都不再被执行了。由于实时进程不会过期，所以属于例外。它们只被移动到其优先级队列的最后面(不会放到过期队列中)。在Linux的早期版本中， sched_yield()的语义有所不同，进程只会被放置到优先级队列的末尾，放弃的时间往往不会太长。现在，应用程序甚至内核代码在调用 sched_yield()前， 应该仔细考虑是否真的希望舍弃处理器时间。

内核代码为了方便，可以直接调用 yield()，先要确定给定进程确实处于可执行状态，然后再调用 sched_yield()。用户空间的应用程序直接使用 sched_yield()系统调用就可以了。

小结

进程调度程序是内核重要的组成部分，因为运行着的进程首先在使用计算机。然而，满足进程调度的各种需要绝不是轻而易举的：很难找到“一刀切”的算法， 既适合众多的可运行进程，又具有可伸缩性，还能在调度周期和吞吐量之间求得平衡，同时还满足各种负载的需求。不过，Linux 内核的新 CFS 调度程序 尽量满足了各个方面的需求，并以较完善的可伸缩性和新颖的方法提供了最佳的解决方案。

系统调用

在现代操作系统中，内核提供了用户进程与内核进行交互的一组接口。这些接口让应用程序受限的访问硬件设备，提供了创建新进程并与已有进程进行通信的机制，也提供了申请操作系统其它资源的能力。这些接口在应用程序 和内核之间扮演了使者的角色，应用程序发出各种请求，而内核负责满足这些请求(或者无法满足时候返回一个错误)。实际上提供这些接口主要是为了保证系统稳定可靠，避免应用程序恣意妄行。

与内核通信

系统调用在用户空间进程和硬件设备之间添加了一个中间层。该层主要作用由三个。受限，它位用户空间提供了一种硬件的抽象接口。距离来说，当需要读写文件的时候，应用程序就可以不去管理磁盘类型和介质， 甚至不用去管文件所在的文件系统到底是哪种类型。第二，系统调用包整了系统的稳定性和安全。作为硬件设备和应用程序之间的中间人，内核可以基于权限、用户类型和其它一些 规则对需要进行的访问进行裁决。举例来说，这样可以避免应用程序不正确的使用硬件设备，窃取其它进程的资源，或是作出其它危害操作系统的事情。 第三，之前曾经提到过，每个基础南横都运行在虚拟系统中，而在用户空间和系统的其余部分提供这样一层公共接口，也是出于这种考虑。如果应用程序可以随意访问硬件而内核又对此一无所知的话，几乎就没法实现 多任务和虚拟内存，当然也不可能实现良好的稳定性和安全性。在 Linux 中，系统调用是用户空间访问内核的唯一手段，除了异常和陷入之外，它们是内核唯一的合法入口，实际上，其它的像 设备文件和/proc之类的方式，最终还是要通过系统调用进行访问的。而有趣的是，Linux提供的系统调用却比大部分操作系统都少得多。

接下来讨论Linux系统调用的规则和实现方法

API、POSIX和C库

一般情况下，应用程序通过在用户空间实现的应用编程接口(API)而不是直接通过系统调用来编程。这点很重要，因为应用程序使用的这种编程接口实际上并不需要和内核提供的系统调用对应。 一个 API 定义了一组应用程序使用的编程接口。它们可以实现成一个系统调用，也可以通过调用多个系统调用来实现，而完全不使用任何系统调用也不存在问题。实际上，API可以在各种不同 的操作系统上实现，给应用程序提供完全相同的接口，而它们本身在这些系统上的实现却可能迥异。下图给出了 POSIX、API、C库以及系统调用之间的关系。

在 Unix 世界中，最流行的应用编程接口是基于 POSIX 标准的。从纯技术的角度来看，POSIX 是由 IEEE 的一组标准组成，其目标是提供一套大体上基于 Unix 的可移植 操作系统标准。在应用场合，Linux尽力与POSIX和SUSv3兼容。

POSIX是说明 API 和系统调用之间关系的一个极好例子。在大多数 Unix 系统上，根据 POSIX 定义的 API 函数和系统调用之间有着直接关系。实际上，POSIX标准就是仿照早期 Unix 系统的接口建立的。另一方面，许多操作系统，像微软的 Windows，尽管是非 Unix 系统，也提供了与 POSIX 兼容的库。
Linux的系统调用像绝大多数 Unix 系统一样，作为 C 库的一部分提供。C库实现了 Unix 系统的主要 API， 包括标准C库函数和系统调用接口。所有的 C 程序都可以使用 C 库，而由于 C 语言本身的特点，其它语言也可以很方便的把它们封装起来使用。此外， C 库提供了 POSIX 的绝大部分 API。
从程序员的角度来看，系统调用无关紧要，它们只需要跟 API 打交道就可以了。相反，内核只跟系统调用打交道；库函数及应用程序是怎么使用系统调用，不是内核 所关心的。但是，内核必须时刻牢记系统调用所有潜在的用途，并保证它们由良好的通用性和灵活性。
关于 Unix 的接口设计由一句格言 “提供机制而不是策略”。换句话说，Unix的系统调用抽象出了用于完成某种确定的目的的函数。至于这些函数怎么用完全不需要内核去关心。

系统调用

要访问系统调用(在Linux中常称为 syscall)，通常通过 C 库中定义的函数调用来进行。它们通常都需要定义零个、一个或几个参数(输入)而且可能产生一些副作用， 例如：写某个文件或向给定的指针拷贝数据等。系统调用还会通过一个 long 类型的返回值来表示成功或者错误。通常，但也不绝对，用一个负的返回值来表明错误。返回一个 0 值通常 表示成功。系统调用在出现错误的时候 C 库会把错误码写入 errno 全局变量。通过调用 perror() 库函数，可以把变量翻译成用户可以理解的错误字符串。

当然，系统调用最终具有一种明确的操作。例如 getpid() 系统调用，根据定义它会返回当前进程的 PID。内核中它的实现非常简单：

1
2
3
4

SYSCALL_DEFINED(getpid)
{
    return task_tgid_vnr(current);  // returns current->tgid
}

注意，定义中并没有规定它要如何实现。内核必须提供系统调用所希望完成的功能，但它完全可以按照自己预期的方式去实现，只要最后的结果正确就行了。当然，上面的系统调用 太简单，也没有什么更多的实现手段。

SYSCALL_DEFINE0 只是一个宏，它定义一个无参数的系统调用(因此这里为数字0)，展开后的代码如下：

1

asmlinkage long sys_getpid(void)

我们看一下如何定义系统调用。首先，注意函数声明中的 asmlinkage限定词，这是一个编译指令，通知编译器仅从栈中提取该函数的参数。所有的系统调用都需要这个限定词。

其次，函数返回 long。为了保证 32位和64位系统的兼容，系统调用在用户空间和内核空间由不同的返回值类型，在用户空间为 int，在内核空间为 long。

最后，注意系统调用 get_pid() 在内核中被定义成 sys_getpid()。这是 Linux 中所有系统调用都应该遵守的命名规则

系统调用号

在 Linux 中，每个系统调用被赋予一个系统调用号。这样，通过这个独一无二的号就可以关联系统调用。当用户空间的进程执行一个系统调用的时候，这个系统 调用号就用来指明到底是要执行哪个系统调用；进程不会提及系统调用的名称。

系统调用号相当重要，一旦分配就不能再有任何变更，否则编译好的应用程序就会崩溃。此外，如果一个系统调用被删除，它所占用的系统调用号也不允许被回收利用， 否则，以前编译过的代码会调用这个系统调用，但事实上却调用的是另一个系统调用。Linux 有一个“未实现”系统调用 sys_ni_syscall() 它返回 除了 -ENOSYS 外不做任何其它工作，这个错误号就是专门针对无效的系统调用而设的。虽然很罕见，但是如果一个系统调用被删除，或者变得不可用，这个函数就要负责 “填补空缺”。

内核记录了系统调用表中的所有已注册过的系统调用的列表，存储在 sys_call_table 中。每一种体系结构中，都明确定义了这个表，在 X86-64 中，它定义于 arch/i386/kernel/syscall_64.c 文件中。这个表为每一个有效的系统调用指定了唯一的系统调用号。

系统调用的性能

Linux 系统调用比其它许多系统执行的要快。Linux很短的上下文切换时间是一个重要原因，进出内核都被优化得简洁高效。另外一个原因是系统调用处理程序和 每个系统调用本身也都非常简洁。

系统调用处理程序

用户空间的程序无法直接执行内核代码。它们不能直接调用内核空间中的函数，因为内核驻留在受保护的地址空间上。如果进程可以直接在内核的地址空间上读写的话，系统的安全性和稳定性 将不复存在。

所以，应用程序应该以某种方式通知系统，告诉内核自己需要执行一个系统调用，希望系统切换到内核态，这样内核就可以代表应用程序在内核空间执行系统调用。

通知内核的机制是靠软中断实现的：通过引发一个异常来促使系统切换到内核态去执行异常处理函数。此时的异常处理程序实际上就是系统调用处理程序。 在 X86 系统上预定义的软中断是中断号 128，通过 int $0x80 指令触发该中断。这条指令会触发一个异常导致系统切换到内核态并执行第 128 号 异常处理程序，而该程序正是系统调用处理程序。这个处理程序名字叫 system_call()。它与硬件体系紧密相关， x86-64 的系统上在 entry_64.S 文件 中用汇编语言编写。最近，x86 处理器增加了一条叫做 sysenter 的指令。与 int 中断指令相比，这条指令提供了更快、更专业的陷入内核执行系统调用的方式。 对这条指令的支持很快被加入内核。且不管系统调用处理程序被如何调用，用户空间引起异常或陷入内核就是一个重要的概念。

指定恰当的系统调用

因为所有的系统调用陷入内核的方式都一样，所以仅仅是陷入内核空间是不够的。因此必须把系统调用号一并传给内核。在 x86 上，系统调用号是通过 eax 寄存器传递给内核的。 在陷入内核之前，用户空间就把相应系统调用所对应的号放入 eax 中。这样系统调用处理程序一旦运行，就可以从 eax 中得到数据。其它体系结构上的实现 也都类似。

system_call()函数通过将给定的系统调用号与 NR_syscalls 做比较来检查其有效性。如果它大于或者等于 NR_syscalls，该函数就返回 -ENOSYS。 否则，就执行相应的系统调用：

1

call* sys_call_table(,%rax,8)

由于系统调用表中的表项是以64位(8字节)类型存放的，所以内核需要将给定的系统调用号乘以 4，然后用所得的结果在该表中查询其位置。在 x86-32 系统上，代码很类似，只是用 4 代替 8

参数传递

除了系统调用号以外，大部分系统调用都还需要一些外部的参数输入。所以，在发生陷入的时候，应该把这些参数从用户空间传给内核。最简单的办法就是像传递系统调用号一样，把这些 参数也存放在寄存器里。在 x86-32 系统上， ebx、ecx、edx 和 edi 按照顺序存放前五个参数。 需要六个或六个以上参数的情况不多见，此时，应该用一个单独的寄存器存放指向所有这些参数在用户空间地址的指针。

给用户空间的返回值也通过寄存器传递。在 X86 系统上，它存放在 eax 寄存器中。

系统调用的实现

实际上，一个 Linux 的系统调用在实现时候并不需要太关心它和系统调用处理程序之间的关系。给 Linux 添加一个新的系统调用是件相对容易的工作。 怎样设计和实现一个系统调用是难题所在，而把它加到内核里却无须太多周折。
接下来关注实现一个新的 Linux 系统调用所需的步骤。

实现系统调用

实现一个新的系统调用的第一步是决定它的用途。每个系统调用都应该有一个明确的用途，Linux中不提倡多用途的系统调用(一个系统调用通过传递不同的参数值来选择完成不同的工作)。 ioctl() 就是一个很好的例子，告诉了我们不应该去做什么。 增加新的系统调用应该考虑以下要求：

• 调用参数、返回值、错误码
• 接口力求简洁、参数尽量少
• 系统调用的语义和行为力求稳定，不做改动
• 设计接口时候尽量为将来多做考虑，系统调用设计的越通用越好(不要设想这个系统调用现在怎么用将来也一定就这么用，系统调用的目的可能不变，但用法可能改变)
• 系统调用的可移植性(别对机器的字节长度和字节序做假设)

记住 Unix 的格言：“提供机制而不是策略”。

参数验证

系统调用必须仔细检查它们所有的参数是否合法有效。系统调用都在内核空间执行，如果任由用户将不合法的输入传递给内核，那么系统的安全和稳定将面临极大的考验。

举例来说，与文件I/O相关的系统调用必须检查文件描述符是否有效、与进程相关的函数必须检查提供的PID是否有效，必须检查每个参数，保证它们不但合法有效，而且正确。 进程不应当让内核去访问那些无权访问的资源。

最重要的一种检查就是检查用户提供的指针是否有效，在接收一个用户空间的指针之前，内核必须保证：

• 指针指向的内存区域属于用户空间。进程决不能哄骗内核去读取内核空间的数据。
• 指针指向的内存区域在进程的地址空间里。进程决不能哄骗内核去读取其它进程的数据。
• 如果是读，该内存应被标记为可读；如果是写，该内存应该被标记为可写；如果是可执行，该内存被标记为可执行。进程决不能绕过内存访问限制。
  

内核提供了两个方法来完成必须的检查和内核空间与用户空间之间数据的来回拷贝。注意，内核无论合适都不能轻率的接收来自用户空间的指针！

• 为了向用户空间写入数据，内核提供了 copy_to_user()，它需要三个参数，第一个是进程空间中的目的内存地址；第二个是内核空间内的源地址；最后 一个参数是需要拷贝的数据长度(字节数)
• 为了从用户空间读取数据，内核提供了 copy_from_user()，它和 copy_to_user() 相似。该函数把第二个参数指定的位置上的数据拷贝到第一个参数指定的位置上，拷贝的数据长度 由第三个参数决定。

如果执行失败，这两个函数返回的都是没能完成拷贝的数据的字节数，如果成功，则返回0.让出现上述错误时候，系统调用返回标准的 -EFAULT。
系统调用 silly_copy()中既有 copy_from_user() 又有 copy_to_user()，它毫无实际用处，让内核空间作为中转站，把用户空间的数据从一个位置复制到另一个位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

SYSCALL_DEFINE3(silly_copy, unsigned long*, src, unsigned long*, dst, unsigned long, len)
{
    unsigned long buf;

    // 将用户地址空间中的 src 拷贝金 buf
    if (copy_from_user(&buf, src, len))
        return -EFAULT;
    
    // 将 buf 拷贝进用户地址空间中的 dst
    if (copy_to_user(dst, &buf, len))
        return -EFAULT;

    // 返回拷贝的数据量
    return len;
}

注意，copy_to_user()和copy_from_user()都有可能引起阻塞。当包含用户数据的页被换出到硬盘上而不是在物理内存上的时候，这种情况就会发生。此时，进程就会休眠，直到 缺页处理程序将该页从硬盘重新换回物理内存。
最后一项检查针对是否合法权限。老版本的Linux内核中，需要超级用户权限的系统调用才可以通过调用 suser() 函数这个标准动作来完成检查。这个函数智能检查 用户是否为超级用户；现在它已经被一个更细粒度的“权能”机制代替。新的系统允许检查针对特定资源的特殊权限。调用者可以使用 capable() 函数来 检查是否有权能对指定的资源进行操作，如果它返回非0值，调用这就有权进行操作，返回0则无权操作。举个例子，capable(CAP_SYS_NICE)可以检查 调用者是否有权改变其它进程的 nice 值。
下面是 reboot*() 系统调用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

SYSCALL_DEFINE4(reboot, int, magic1, int, magic2, unsigned int, cmd, void __user*, arg)
{
    char buffer[256];

    if (!capable(CAP_SYS_BOOT))
        return -EPERM;

    // 为了安全起见，我们需要 “magic” 参数
    if (magic1 != LINUX_REBOOT_MAGIC1 
        || (magic2 != LINUX_REBOOT_MAGIC2
             && magic2 != LINUX_REBOOT_MAGIC2A 
             && magic2 != LINUX_REBOOT_MAGIC2B
             && magic2 != LINUX_REBOOT_MAGIC2C))
        return -EINVAL;

    // 当未设置 pm_power_off 时候，请不要试图让 power_off 的代码看起来像是可以停机，而应该采用更简单的方式
    if ((cmd == LINUX_REBOOT_CMD_POWER_OFF) && !pm_power_off)
        cmd = LINUX_REBOOT_CMD_HALT;

    lock_kernel();
    switch (cmd) {
    case LINUX_REBOOT_CMD_RESTART: {
        kernel_restart(NULL);
        break;
    }
    case LINUX_REBOOT_CMD_CAD_ON: {
        C_A_D = 1;
        break;
    }
    case LINUX_REBOOT_CMD_CAD_OFF: {
        C_A_D = 0;
        break;
    }
    case LINUX_REBOOT_CMD_HALT: {
        kernel_halt();
        unlock_kernel();
        do_exit(0);
        break;
    }
    case LINUX_REBOOT_CMD_POWER_OFF: {
        kernel_power_off();
        unlock_kernel();
        do_exit(0);
        break;
    }
    case LINUX_REBOOT_CMD_RESTART2: {
        if (strncpy_from_user(&buffer[0], arg,sizeof(buffer) - 1) < 0) {
            unlock_kernel();
            return -EFAULT;
        }
        buffer[sizeof(buffer) - 1] = '\0';
        kernel_restart(buffer);
        break;
    }
    default: {
        unlock_kernel();
        return -EINVAL;
    }
    }
    unlock_kernel();

    return 0;
}

参见<linux/capability.h>，其中包含一份所有这些权能和其对应的权限的列表。

系统调用上下文

内核在执行系统调用的时候处于进程上下文。current 指针指向当前任务，即引发系统调用的那个进程。