用C/C++开发的程序执行效率很高，但却经常受到内存泄漏的困扰。本文提供一种通过wrap malloc查找memory leak的思路，依靠这个方法，笔者紧急解决了内存泄漏问题，避免项目流血上大促，该方法在日后工作中大放光彩，发现了项目中大量沉疴已久的内存泄漏问题。

什么是内存泄漏？

动态申请的内存丢失引用，造成没有办法回收它（我知道杠jing要说进程退出前系统会统一回收），这便是内存泄漏。

Java等编程语言会自动管理内存回收，而C/C++需要显式的释放，有很多手段可以避免内存泄漏，比如RAII，比如智能指针（大多基于引用计数计数），比如内存池。

理论上，只要我们足够小心，在每次申请的时候，都牢记释放，那这个世界就清净了，但现实往往没有那么美好，比如抛异常了，释放内存的语句执行不到，又或者某菜鸟程序员不小心埋了一个雷，所以，我们必须直面真实的世界，那就是我们会遭遇内存泄漏。

怎么查内存泄漏？

我们可以review代码，但从海量代码里找到隐藏的问题，这如同大海捞针，往往两手空空。

所以，我们需要借助工具，比如valgrind，但这些找内存泄漏的工具，往往对你使用动态内存的方式有某种期待，或者说约束，比如常驻内存的对象会被误报出来，然后真正有用的信息会掩盖在误报的汪洋大海里。很多时候，甚至valgrind根本解决不了日常项目中的问题。

所以很多著名的开源项目，为了能用valgrind跑，都费大力气，大幅修改源代码，从而使得项目符合valgrind的要求，满足这些要求，用valgrind跑完没有任何报警的项目叫valgrind干净。

既然这些玩意儿都中看不中用，所以，求人不如求己，还是得自力更生。

什么是动态内存分配器？

动态内存分配器是介于kernel跟应用程序之间的一个函数库，glibc提供的动态内存分配器叫ptmalloc，它也是应用最广泛的动态内存分配器实现。

从kernel角度看，动态内存分配器属于应用程序层；而从应用程序的角度看，动态内存分配器属于系统层。

应用程序可以通过mmap系统直接向kernel申请动态内存，也可以通过动态内存分配器的malloc接口分配内存，而动态内存分配器会通过sbrk、mmap向kernel分配内存，所以应用程序通过free释放的内存，并不一定会真正返还给系统，它也有可能被动态内存分配器缓存起来。

google有自己的动态内存分配器tcmalloc，另外jemalloc也是著名的动态内存分配器，他们有不同的性能表现，也有不同的缓存和分配策略。你可以用它们替换linux系统glibc自带的ptmalloc。

new/delete跟malloc/free的关系

new是c++的用法，比如Foo *f = new Foo，其实它分为3步。

1. 通过operator new()分配sizeof(Foo)的内存，最终通过malloc分配。
2. 在新分配的内存上构建Foo对象。
3. 返回新构建的对象地址。

new=分配内存+构造+返回，而delete则是等于析构+free。所以搞定malloc、free就是从根本上搞定动态内存分配。

chunk

每次通过malloc返回的一块内存叫一个chunk，动态内存分配器是这样定义的，后面我们都这样称呼。

wrap malloc

gcc支持wrap，即通过传递-Wl,--wrap,malloc的方式，可以改变调用malloc的行为，把对malloc的调用链接到自定义的__wrap_malloc(size_t)函数，而我们可以在__wrap_malloc(size_t)函数的实现中通过__real_malloc(size_t)真正分配内存，而后我们可以做搞点小动作。

同样，我们可以wrap free。malloc跟free是配对的，当然也有其他相关API，比如calloc、realloc、valloc，但这根本上还是malloc+free，比如realloc就是malloc + free。

怎么去定位内存泄漏呢？

我们会malloc各种不同size的chunk，也就是每种不同size的chunk会有不同数量，如果我们能够跟踪每种size的chunk数量，那就可以知道哪种size的chunk在泄漏。很简单，如果该size的chunk数量一直在增长，那它很可能泄漏。

光知道某种size的chunk泄漏了还不够，我们得知道是哪个调用路径上导致该size的chunk被分配，从而去检查是不是正确释放了。

怎么跟踪到每种size的chunk数量？

我们可以维护一个全局 unsigned int malloc_map[1024 * 1024]数组，该数组的下标就是chunk的size，malloc_map[size]的值就对应到该size的chunk分配量。

这等于维护了一个chunk size到chunk count的映射表，它足够快，而且它可以覆盖到0 ~ 1M大小的chunk的范围，它已经足够大了，试想一次分配一兆的块已经很恐怖了，可以覆盖到大部分场景。

那大于1M的块怎么办呢？我们可以通过log记录下来。

• 在__wrap_malloc里，++malloc_map[size]
• 在__wrap_free里，--malloc_map[size]

很简单，我们通过malloc_map记录了各size的chunk的分配量。

如何知道释放的chunk的size？

不对，free(void *p)只有一个参数，我如何知道释放的chunk的size呢？怎么办？

我们通过在__wrap_malloc(size_t)的时候，分配8+size的chunk，也就是多分配8字节，开始的8字节存储该chunk的size，然后返回的是(char*)chunk + 8，也就是偏移8个字节返回给调用malloc的应用程序。

这样在free的时候，传入参数void* p，我们把p往前移动8个字节，解引用就能得到该chunk的大小，而该大小值就是前一步，在__wrap_malloc的时候设置的size。

好了，我们真正做到记录各size的chunk数量了，它就存在于malloc_map[1M]的数组中，假设64个字节的chunk一直在被分配，数量一直在增长，我们觉得该size的chunk很有可能泄漏，那怎么定位到是哪里调用过来的呢？

如何记录调用链？

我们可以维护一个toplist数组，该数组假设有10个元素，它保存的是chunk数最大的10种size，这个很容易做到，通过对malloc_map取top 10就行。

然后我们在__wrap_malloc(size_t)里，测试该size是不是toplist之一，如果是的话，那我们通过glibc的backtrace把调用堆栈dump到log文件里去。

注意：这里不能再分配内存，所以你只能使用backtrace，而不能使用backtrace_symbols，这样你只能得到调用堆栈的符号地址，而不是符号名。

如何把符号地址转换成符号名，也就是对应到代码行呢？

addr2line

addr2line工具可以做到，你可以追查到调用链，进而定位到内存泄漏的问题。

至此，你已经get到了整个核心思想。

当然，实际项目中，我们做的更多，我们不仅仅记录了toplist size，还记录了各size chunk的增量toplist，会记录大块的malloc/free，会wrap更多的API。

总结一下：通过wrap malloc/free + backtrace + addr2line，你就可以定位到内存泄漏了，恭喜大家。

使用valgrind

valgrind是什么？

Valgrind是一套Linux下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind由内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模拟了一个CPU环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内核提供的服务完成各种特定的内存调试任务。Valgrind的体系结构如下图所示：

Valgrind包括如下一些工具：

Memcheck

最常用的工具，用来检测程序中出现的内存问题，所有对内存的读写都会被检测到，一切对malloc()/free()/new/delete的调用都会被捕获。所以，它能检测以下问题：

• 对未初始化内存的使用；
• 读/写释放后的内存块；
• 读/写超出malloc分配的内存块；
• 读/写不适当的栈中内存块；
• 内存泄漏，指向一块内存的指针永远丢失；
• 不正确的malloc/free或new/delete匹配；
• memcpy()相关函数中的dst和src指针重叠。

Callgrind

和gprof类似的分析工具，但它对程序的运行观察更是入微，能给我们提供更多的信息。和gprof不同，它不需要在编译源代码时附加特殊选项，但加上调试选项是推荐的。Callgrind收集程序运行时的一些数据，建立函数调用关系图，还可以有选择地进行cache模拟。在运行结束时，它会把分析数据写入一个文件。callgrind_annotate可以把这个文件的内容转化成可读的形式。

Cachegrind

Cache分析器，它模拟CPU中的一级缓存I1，Dl和二级缓存，能够精确地指出程序中cache的丢失和命中。如果需要，它还能够为我们提供cache丢失次数，内存引用次数，以及每行代码，每个函数，每个模块，整个程序产生的指令数。这对优化程序有很大的帮助。

Helgrind

它主要用来检查多线程程序中出现的竞争问题。Helgrind寻找内存中被多个线程访问，而又没有一贯加锁的区域，这些区域往往是线程之间失去同步的地方，而且会导致难以发掘的错误。Helgrind实现了名为“Eraser”的竞争检测算法，并做了进一步改进，减少了报告错误的次数。不过，Helgrind仍然处于实验阶段。

Massif

堆栈分析器，它能测量程序在堆栈中使用了多少内存，告诉我们堆块，堆管理块和栈的大小。Massif能帮助我们减少内存的使用，在带有虚拟内存的现代系统中，它还能够加速我们程序的运行，减少程序停留在交换区中的几率。

此外，lackey和nulgrind也会提供。Lackey是小型工具，很少用到；Nulgrind只是为开发者展示如何创建一个工具。

原理

一个典型的Linux C程序内存空间由如下几部分组成：

• 代码段（.text）。这里存放的是CPU要执行的指令。代码段是可共享的，相同的代码在内存中只会有一个拷贝，同时这个段是只读的，防止程序由于错误而修改自身的指令。
• 初始化数据段（.data）。这里存放的是程序中需要明确赋初始值的变量，例如位于所有函数之外的全局变量：int val=”100”。需要强调的是，以上两段都是位于程序的可执行文件中，内核在调用exec函数启动该程序时从源程序文件中读入。
• 未初始化数据段（.bss）。位于这一段中的数据，内核在执行该程序前，将其初始化为0或者null。例如出现在任何函数之外的全局变量：int sum;
• 堆（Heap）。这个段用于在程序中进行动态内存申请，例如经常用到的malloc，new系列函数就是从这个段中申请内存。
• 栈（Stack）。函数中的局部变量以及在函数调用过程中产生的临时变量都保存在此段中。

Memcheck 能够检测出内存问题，关键在于其建立了两个全局表。

• Valid-Value 表：
  • 对于进程的整个地址空间中的每一个字节(byte)，都有与之对应的 8 个 bits；对于 CPU 的每个寄存器，也有一个与之对应的 bit 向量。这些 bits 负责记录该字节或者寄存器值是否具有有效的、已初始化的值。
• Valid-Address 表
• 对于进程整个地址空间中的每一个字节(byte)，还有与之对应的 1 个 bit，负责记录该地址是否能够被读写。

检测原理

当要读写内存中某个字节时，首先检查这个字节对应的 A bit。如果该A bit显示该位置是无效位置，memcheck 则报告读写错误。

内核（core）类似于一个虚拟的 CPU 环境，这样当内存中的某个字节被加载到真实的 CPU 中时，该字节对应的 V bit 也被加载到虚拟的 CPU 环境中。一旦寄存器中的值，被用来产生内存地址，或者该值能够影响程序输出，则 memcheck 会检查对应的V bits，如果该值尚未初始化，则会报告使用未初始化内存错误。

Valgrind 使用

用法: valgrind [options] prog-and-args

• [options]：常用选项，适用于所有Valgrind工具
• -tool=<name>：最常用的选项。运行 valgrind中名为toolname的工具。默认memcheck。
• h –help：显示帮助信息。
• -version：显示valgrind内核的版本，每个工具都有各自的版本。
• q –quiet：安静地运行，只打印错误信息。
• v –verbose：更详细的信息, 增加错误数统计。
• -trace-children=no|yes：跟踪子线程? [no]
• -track-fds=no|yes：跟踪打开的文件描述？[no]
• -time-stamp=no|yes：增加时间戳到LOG信息? [no]
• -log-fd=<number>：输出LOG到描述符文件 [2=stderr]
• -log-file=<file>：将输出的信息写入到filename.PID的文件里，PID是运行程序的进行ID
• -log-file-exactly=<file>：输出LOG信息到 file
• -log-file-qualifier=<VAR>：取得环境变量的值来做为输出信息的文件名。 [none]
• -log-socket=ipaddr:port：输出LOG到socket ，ipaddr:port

LOG信息输出

• -xml=yes：将信息以xml格式输出，只有memcheck可用
• -num-callers=<number> show <number>：callers in stack traces [12]
• -error-limit=no|yes：如果太多错误，则停止显示新错误? [yes]
• -error-exitcode=<number>：如果发现错误则返回错误代码 [0=disable]
• -db-attach=no|：当出现错误，valgrind会自动启动调试器gdb。[no]
• -db-command=<command>：启动调试器的命令行选项 [gdb -nw %f %p]

适用于Memcheck工具的相关选项：

• -leak-check=no|summary|full：要求对leak给出详细信息? [summary]
• -leak-resolution=low|med|high：how much bt merging in leak check [low]
• -show-reachable=no|yes：show reachable blocks in leak check? [no]

Valgrind 使用举例（一）

1

mpirun -n 12 valgrind run/cpl/c_coupler/exe/c_coupler : -n 10 valgrind run/atm/gamil/exe/gamil : -n 4 valgrind run/ocn/licom/exe/licom : -n 4 valgrind run/sice/cice/exe/cice : -n 4 valgrind run/lnd/clm/exe/clm

下面是一段有问题的C程序代码test.c

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

# include <stdlib.h>
void f(void)
{
   int* x = malloc(10 * sizeof(int));
   x[10] = 0;  //问题1: 数组下标越界
}                  //问题2: 内存没有释放

int main(void)
{
   f();
   return 0;
 }

valgrind --tool=memcheck --leak-check=full ./test

问题分析：

• 对于位于程序中不同段的变量，其初始值是不同的，全局变量和静态变量初始值为0，而局部变量和动态申请的变量，其初始值为随机值。如果程序使用了为随机值的变量，那么程序的行为就变得不可预期。

数组越界/内存未释放

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

#include<stdlib.h>
void k(void)
{
    int *x = malloc(8 * sizeof(int));
    x[9] = 0; //数组下标越界
} //内存未释放

int main(void)
{
    k();
    return 0;
}

1）编译程序test.c

1

gcc -Wall test.c -g -o test #Wall提示所有告警，-g 调试信息，-o输出

2）使用Valgrind检查程序BUG

1
2

valgrind --tool=memcheck --leak-check=full ./test
#--leak-check=full 所有泄露检查

3) 运行结果如下：

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

==2989== Memcheck, a memory error detector
==2989== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward
et al.
==2989== Using Valgrind-3.8.1 and LibVEX; rerun with -h for
copyright info
==2989== Command: ./test
==2989==
==2989== Invalid write of size 4
==2989== at 0x4004E2: k (test.c:5)
==2989== by 0x4004F2: main (test.c:10)
==2989== Address 0x4c27064 is 4 bytes after a block of size 32 alloc'd
==2989== at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==2989== by 0x4004D5: k (test.c:4)
==2989== by 0x4004F2: main (test.c:10)
==2989==
==2989==
==2989== HEAP SUMMARY:
==2989== in use at exit: 32 bytes in 1 blocks
==2989== total heap usage: 1 allocs, 0 frees, 32 bytes allocated
==2989==
==2989== 32 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2989== at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==2989== by 0x4004D5: k (test.c:4)
==2989== by 0x4004F2: main (test.c:10)
==2989==
==2989== LEAK SUMMARY:
==2989== definitely lost: 32 bytes in 1 blocks
==2989== indirectly lost: 0 bytes in 0 blocks
==2989== possibly lost: 0 bytes in 0 blocks
==2989== still reachable: 0 bytes in 0 blocks
==2989==suppressed: 0 bytes in 0 blocks
==2989==
==2989== For counts of detected and suppressed errors, rerun with: -v
==2989== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 6 from 6)

内存释放后读写

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

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    char *p = malloc(1); //分配
    *p = 'a';

    char c = *p;

    printf("\n [%c]\n",c);

    free(p); //释放
    c = *p; //取值
    return 0;
}

1）编译程序t2.c

1

gcc -Wall t2.c -g -o t2

2）使用Valgrind检查程序BUG

1

valgrind --tool=memcheck --leak-check=full ./t2

3) 运行结果如下：

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

==3058== Memcheck, a memory error detector
==3058== Copyright (C) 2002-2012, and GNU GPL'd, by Julian
Seward et al.
==3058== Using Valgrind-3.8.1 and LibVEX; rerun with -h
for copyright info
==3058== Command: ./t2
==3058==

[a]
==3058== Invalid read of size 1
==3058== at 0x4005A3: main (t2.c:14)
==3058== Address 0x4c27040 is 0 bytes inside a block of size
1 free'd
==3058== at 0x4A06430: free (vg_replace_malloc.c:446)
==3058== by 0x40059E: main (t2.c:13)
==3058==
==3058==
==3058== HEAP SUMMARY:
==3058== in use at exit: 0 bytes in 0 blocks
==3058== total heap usage: 1 allocs, 1 frees, 1 bytes allocated
==3058==
==3058== All heap blocks were freed -- no leaks are possible
==3058==
==3058== For counts of detected and suppressed errors, rerun with:
-v
==3058== ERROR SUMMARY: 1 errors from 1 contexts
(suppressed: 6 from 6)

从上输出内容可以看到，Valgrind检测到无效的读取操作然后输出“Invalid read of size 1”。

无效读写

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

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    char *p = malloc(1); //分配1字节
    *p = 'a';
    char c = *(p+1); //地址加1
    printf("\n [%c]\n",c);
    free(p);
    return 0;
}

1）编译程序t3.c

1

gcc -Wall t3.c -g -o t3

2）使用Valgrind检查程序BUG

1

valgrind --tool=memcheck --leak-check=full ./t3

3) 运行结果如下：

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

==3128== Memcheck, a memory error detector
==3128== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==3128== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==3128== Command: ./t3
==3128==
==3128== Invalid read of size 1 #无效读取
==3128==at 0x400579: main (t3.c:9)
==3128==Address 0x4c27041 is 0 bytes after a block of size 1 alloc'd
==3128==at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==3128==by 0x400565: main (t3.c:6)
==3128==[]
==3128==
==3128== HEAP SUMMARY:
==3128==in use at exit: 0 bytes in 0 blocks
==3128==total heap usage: 1 allocs, 1 frees, 1 bytes allocated
==3128==
==3128== All heap blocks were freed -- no leaks are possible
==3128==
==3128== For counts of detected and suppressed errors, rerun with: -v
==3128== ERROR SUMMARY: 1 errors from 1 contexts
(suppressed: 6 from 6)

内存泄露

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *p = malloc(1);
    *p = 'x';
    char c = *p;
    printf("%c\n",c); //申请后未释放
    return 0;
}

1）编译程序t4.c

1

gcc -Wall t4.c -g -o t4

2）使用Valgrind检查程序BUG

1

valgrind --tool=memcheck --leak-check=full ./t4

3) 运行结果如下：

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

==3221== Memcheck, a memory error detector
==3221== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==3221== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==3221== Command: ./t4
==3221==
==3221== Invalid write of size 4
==3221==at 0x40051E: main (t4.c:7)
==3221==Address 0x4c27040 is 0 bytes inside a block of size 1 alloc'd
==3221==at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==3221==by 0x400515: main (t4.c:6)
==3221==
==3221== Invalid read of size 4
==3221==at 0x400528: main (t4.c:8)
==3221==Address 0x4c27040 is 0 bytes inside a block of size 1 alloc'd
==3221==at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==3221==by 0x400515: main (t4.c:6)
==3221==
==3221==
==3221== HEAP SUMMARY:
==3221==in use at exit: 1 bytes in 1 blocks
==3221==total heap usage: 1 allocs, 0 frees, 1 bytes allocated
==3221==
==3221== 1 bytes in 1 blocks are definitely lost in loss record 1 of 1
==3221==at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==3221==by 0x400515: main (t4.c:6)
==3221==
==3221== LEAK SUMMARY:
==3221==definitely lost: 1 bytes in 1 blocks
==3221==indirectly lost: 0 bytes in 0 blocks
==3221== possibly lost: 0 bytes in 0 blocks
==3221==still reachable: 0 bytes in 0 blocks
==3221== suppressed: 0 bytes in 0 blocks
==3221==
==3221== For counts of detected and suppressed errors, rerun with: -v
==3221== ERROR SUMMARY: 3 errors from 3 contexts
(suppressed: 6 from 6)

从检查结果看，可以发现内存泄露。

内存多次释放

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

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    char *p;
    p=(char *)malloc(100);
    if(p)
        printf("Memory Allocated at: %s/n",p);
    else
        printf("Not Enough Memory!/n");
    free(p); //重复释放
    free(p);
    free(p);
    return 0;
}

1）编译程序t5.c

1

gcc -Wall t5.c -g -o t5

2）使用Valgrind检查程序BUG

1

valgrind --tool=memcheck --leak-check=full ./t5

3) 运行结果如下：

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

==3294== Memcheck, a memory error detector
==3294== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==3294== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==3294== Command: ./t5
==3294==
==3294== Conditional jump or move depends on uninitialised value(s)
==3294== at 0x3CD4C47E2C: vfprintf (in /lib64/libc-2.12.so)
==3294== by 0x3CD4C4F189: printf (in /lib64/libc-2.12.so)
==3294== by 0x400589: main (t5.c:9)
==3294==
==3294== Invalid free() / delete / delete[] / realloc()
==3294== at 0x4A06430: free (vg_replace_malloc.c:446)
==3294== by 0x4005B5: main (t5.c:13)
==3294== Address 0x4c27040 is 0 bytes inside a block of size
100 free'd
==3294== at 0x4A06430: free (vg_replace_malloc.c:446)
==3294== by 0x4005A9: main (t5.c:12)
==3294==
==3294== Invalid free() / delete / delete[] / realloc()
==3294== at 0x4A06430: free (vg_replace_malloc.c:446)
==3294== by 0x4005C1: main (t5.c:14)
==3294== Address 0x4c27040 is 0 bytes inside a block of size
100 free'd
==3294== at 0x4A06430: free (vg_replace_malloc.c:446)
==3294== by 0x4005A9: main (t5.c:12)
==3294==
Memory Allocated at: /n==3294==
==3294== HEAP SUMMARY:
==3294== in use at exit: 0 bytes in 0 blocks
==3294== total heap usage: 1 allocs, 3 frees, 100 bytes allocated

从上面的输出可以看到(标注), 该功能检测到我们对同一个指针调用了3次释放内存操作。

内存动态管理

常见的内存分配方式分三种：静态存储，栈上分配，堆上分配。全局变量属于静态存储，它们是在编译时就被分配了存储空间，函数内的局部变量属于栈上分配，而最灵活的内存使用方式当属堆上分配，也叫做内存动态分配了。常用的内存动态分配函数包括：malloc, alloc, realloc, new等，动态释放函数包括free, delete。

一旦成功申请了动态内存，我们就需要自己对其进行内存管理，而这又是最容易犯错误的。下面的一段程序，就包括了内存动态管理中常见的错误。

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

#include <stdio.h>
#include <stdlib.h>
int main(int argc,char *argv[])
{
    int i;
    char* p = (char*)malloc(10);
    char* pt=p;
    for(i = 0;i < 10;i++)
    {
        p[i] = 'z';
    }
    free(p);
    pt[1] = 'x';
    free(pt);
    return 0;
}

1）编译程序t6.c

1

gcc -Wall t6.c -g -o t6

2）使用Valgrind检查程序BUG

1

valgrind --tool=memcheck --leak-check=full ./t6

3) 运行结果如下：

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

==3380== Memcheck, a memory error detector
==3380== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==3380== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==3380== Command: ./t6
==3380==
==3380== Invalid write of size 1
==3380==at 0x40055C: main (t6.c:14)
==3380==Address 0x4c27041 is 1 bytes inside a block of size 10 free'd
==3380==at 0x4A06430: free (vg_replace_malloc.c:446)
==3380==by 0x400553: main (t6.c:13)
==3380==
==3380== Invalid free() / delete / delete[] / realloc()
==3380==at 0x4A06430: free (vg_replace_malloc.c:446)
==3380==by 0x40056A: main (t6.c:15)
==3380==Address 0x4c27040 is 0 bytes inside a block of size 10 free'd
==3380==at 0x4A06430: free (vg_replace_malloc.c:446)
==3380==by 0x400553: main (t6.c:13)
==3380==
==3380==
==3380== HEAP SUMMARY:
==3380==in use at exit: 0 bytes in 0 blocks
==3380==total heap usage: 1 allocs, 2 frees, 10 bytes allocated

申请内存在使用完成后就要释放。如果没有释放，或少释放了就是内存泄露；多释放也会产生问题。上述程序中，指针p和pt指向的是同一块内存，却被先后释放两次。系统会在堆上维护一个动态内存链表，如果被释放，就意味着该块内存可以继续被分配给其他部分，如果内存被释放后再访问，就可能覆盖其他部分的信息，这是一种严重的错误，上述程序第14行中就在释放后仍然写这块内存。

输出结果显示，第13行分配和释放函数不一致；第14行发生非法写操作，也就是往释放后的内存地址写值；第15行释放内存函数无效。

massif

Massif 命令行选项

关于 massif 命令行选项，可以直接查看 valgrind 的 help 信息：

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
64
65
66
67

MASSIF OPTIONS
       --heap=<yes|no> [default: yes]
           Specifies whether heap profiling should be done.

       --heap-admin=<size> [default: 8]
           If heap profiling is enabled, gives the number of administrative bytes per block to use. This should be an estimate of the average, since it may vary. For example, the
           allocator used by glibc on Linux requires somewhere between 4 to 15 bytes per block, depending on various factors. That allocator also requires admin space for freed blocks,
           but Massif cannot account for this.

       --stacks=<yes|no> [default: no]
           Specifies whether stack profiling should be done. This option slows Massif down greatly, and so is off by default. Note that Massif assumes that the main stack has size zero
           at start-up. This is not true, but doing otherwise accurately is difficult. Furthermore, starting at zero better indicates the size of the part of the main stack that a user
           program actually has control over.

       --pages-as-heap=<yes|no> [default: no]
           Tells Massif to profile memory at the page level rather than at the malloc'd block level. See above for details.

       --depth=<number> [default: 30]
           Maximum depth of the allocation trees recorded for detailed snapshots. Increasing it will make Massif run somewhat more slowly, use more memory, and produce bigger output
           files.

       --alloc-fn=<name>
           Functions specified with this option will be treated as though they were a heap allocation function such as malloc. This is useful for functions that are wrappers to malloc or
           new, which can fill up the allocation trees with uninteresting information. This option can be specified multiple times on the command line, to name multiple functions.

           Note that the named function will only be treated this way if it is the top entry in a stack trace, or just below another function treated this way. For example, if you have a
           function malloc1 that wraps malloc, and malloc2 that wraps malloc1, just specifying --alloc-fn=malloc2 will have no effect. You need to specify --alloc-fn=malloc1 as well.
           This is a little inconvenient, but the reason is that checking for allocation functions is slow, and it saves a lot of time if Massif can stop looking through the stack trace
           entries as soon as it finds one that doesn't match rather than having to continue through all the entries.

           Note that C++ names are demangled. Note also that overloaded C++ names must be written in full. Single quotes may be necessary to prevent the shell from breaking them up. For
           example:

               --alloc-fn='operator new(unsigned, std::nothrow_t const&)'

       --ignore-fn=<name>
           Any direct heap allocation (i.e. a call to malloc, new, etc, or a call to a function named by an --alloc-fn option) that occurs in a function specified by this option will be
           ignored. This is mostly useful for testing purposes. This option can be specified multiple times on the command line, to name multiple functions.

           Any realloc of an ignored block will also be ignored, even if the realloc call does not occur in an ignored function. This avoids the possibility of negative heap sizes if
           ignored blocks are shrunk with realloc.

           The rules for writing C++ function names are the same as for --alloc-fn above.

       --threshold=<m.n> [default: 1.0]
           The significance threshold for heap allocations, as a percentage of total memory size. Allocation tree entries that account for less than this will be aggregated. Note that
           this should be specified in tandem with ms_print's option of the same name.

       --peak-inaccuracy=<m.n> [default: 1.0]
           Massif does not necessarily record the actual global memory allocation peak; by default it records a peak only when the global memory allocation size exceeds the previous peak
           by at least 1.0%. This is because there can be many local allocation peaks along the way, and doing a detailed snapshot for every one would be expensive and wasteful, as all
           but one of them will be later discarded. This inaccuracy can be changed (even to 0.0%) via this option, but Massif will run drastically slower as the number approaches zero.

       --time-unit=<i|ms|B> [default: i]
           The time unit used for the profiling. There are three possibilities: instructions executed (i), which is good for most cases; real (wallclock) time (ms, i.e. milliseconds),
           which is sometimes useful; and bytes allocated/deallocated on the heap and/or stack (B), which is useful for very short-run programs, and for testing purposes, because it is
           the most reproducible across different machines.

       --detailed-freq=<n> [default: 10]
           Frequency of detailed snapshots. With --detailed-freq=1, every snapshot is detailed.

       --max-snapshots=<n> [default: 100]
           The maximum number of snapshots recorded. If set to N, for all programs except very short-running ones, the final number of snapshots will be between N/2 and N.

       --massif-out-file=<file> [default: massif.out.%p]
           Write the profile data to file rather than to the default output file, massif.out.<pid>. The %p and %q format specifiers can be used to embed the process ID and/or the
           contents of an environment variable in the name, as is the case for the core option --log-file.

对其中几个常用的选项做一个说明：

• –stacks: 栈内存的采样开关，默认关闭。打开后，会针对栈上的内存也进行采样，会使 massif 性能变慢；
• –time-unit：指定用来分析的时间单位。这个选项三个有效值：执行的指令（i），即默认值，用于大多数情况；即时（ms，单位毫秒），可用于某些特定事务；以及在堆（/或者）栈中分配/取消分配的字节（B），用于很少运行的程序，且用于测试目的，因为它最容易在不同机器中重现。这个选项在使用 ms_print 输出结果画图是游泳
• –detailed-freq: 针对详细内存快照的频率，默认是 10， 即每 10 个快照会有采集一个详细的内存快照
• –massif-out-file： 采样结束后，生成的采样文件（后续可以使用 ms_print 或者 massif-visualizer 进行分析）

开始采集

经过上面的了解，接下来可以开始内存数据采集了，假设我们需要采集的二进制程序名为 xprogram:

1

valgrind -v --tool=massif --time-unit=B --detailed-freq=1 --massif-out-file=./massif.out  ./xprogram someargs

运行一段时间后，采集到足够多的内存数据之后，我们需要停止程序，让它生成采集的数据文件，使用 kill 命令让 valgrind 程序退出。

attention: 这里禁止使用 kill -9 模式去杀进程，不然不会产生采样文件

ms_print 分析采样文件

ms_print 是用来分析 massif 采样得到的内存数据文件的，使用命令为：

1

ms_print ./massif.out

或者把输出保存到文件：

1

ms_print ./massif.out > massif.result

打开 massif.result 看看长啥样：

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

--------------------------------------------------------------------------------
Command:            ./xprogram someargs
Massif arguments:   --time-unit=B --massif-out-file=./massif.out
ms_print arguments: massif.out
--------------------------------------------------------------------------------


    GB
1.279^                                                                       #
     |                                                                       #
     |                                                                   @  @#
     |                                                                   @::@#
     |                                                                 @:@: @#
     |                                                            @::  @:@: @#
     |                                                      : ::::@: ::@:@: @#
     |                                             @ @@@@ :::::: :@: : @:@: @#
     |                                          :  @:@ @ @: :::: :@: : @:@: @#
     |                                     @  :::::@:@ @ @: :::: :@: : @:@: @#
     |                               @@:::@@::: :: @:@ @ @: :::: :@: : @:@: @#
     |                            :::@ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |                    :: @@::::: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |                 :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |          @  :::::::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |        ::@::: : :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |      ::::@: : : :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |     :: ::@: : : :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     |   @@:: ::@: : : :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
     | ::@ :: ::@: : : :::: :@ :: :: @ : :@@: : :: @:@ @ @: :::: :@: : @:@: @#
   0 +----------------------------------------------------------------------->GB
     0                                                                   813.9

Number of snapshots: 68
 Detailed snapshots: [2, 7, 16, 21, 24, 25, 30, 32, 33, 34, 41, 44, 46, 48, 51, 52, 58, 59, 61, 64, 65, 66, 67 (peak)]

这张图大概意思就表示堆内存的分配量随着采样时间的变化。从上图可以看到堆内存一直在增长，可能存在一些内存泄露等问题。

往下看还能看到内存的分配栈：

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

  0              0                0                0             0            0
  1 20,021,463,688      133,278,776      124,687,612     8,591,164            0
  2 45,201,848,936      204,228,232      191,089,596    13,138,636            0
93.57% (191,089,596B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->41.07% (83,886,080B) 0xF088E6: rocksdb::Arena::AllocateNewBlock(unsigned long) (in /chain/xtopchain)
| ->41.07% (83,886,080B) 0xF08500: rocksdb::Arena::AllocateFallback(unsigned long, bool) (in /chain/xtopchain)
|   ->41.07% (83,886,080B) 0xF0886C: rocksdb::Arena::AllocateAligned(unsigned long, unsigned long, rocksdb::Logger*) (in /chain/xtopchain)
|     ->41.07% (83,886,080B) 0xDE62BC: rocksdb::ConcurrentArena::AllocateAligned(unsigned long, unsigned long, rocksdb::Logger*)::{lambda()
|     | ->41.07% (83,886,080B) 0xDE7D9A: char* rocksdb::ConcurrentArena::AllocateImpl<rocksdb::ConcurrentArena::AllocateAligned(unsigned long, unsigned long, rocksdb::Logger*)::{lambda()
|     |   ->41.07% (83,886,080B) 0xDE6371: rocksdb::ConcurrentArena::AllocateAligned(unsigned long, unsigned long, rocksdb::Logger*) (in /chain/xtopchain)
|     |     ->41.07% (83,886,080B) 0xE6FAB0: rocksdb::InlineSkipList<rocksdb::MemTableRep::KeyComparator const&>::AllocateNode(unsigned long, int) (in /chain/xtopchain)
|     |       ->41.07% (83,886,080B) 0xE6F472: rocksdb::InlineSkipList<rocksdb::MemTableRep::KeyComparator const&>::AllocateKey(unsigned long) (in /chain/xtopchain)
|     |         ->41.07% (83,886,080B) 0xE6E40A: rocksdb::(anonymous namespace)::SkipListRep::Allocate(unsigned long, char**) (in /chain/xtopchain)
|     |           ->41.07% (83,886,080B) 0xDE32E3: rocksdb::MemTable::Add(unsigned long, rocksdb::ValueType, rocksdb::Slice const&, rocksdb::Slice const&, bool, rocksdb::MemTablePostProcessInfo*) (in /chain/xtopchain)
|     |             ->41.07% (83,886,080B) 0xE5C218: rocksdb::MemTableInserter::PutCFImpl(unsigned int, rocksdb::Slice const&, rocksdb::Slice const&, rocksdb::ValueType) (in /chain/xtopchain)
|     |               ->41.07% (83,886,080B) 0xE5C92C: rocksdb::MemTableInserter::PutCF(unsigned int, rocksdb::Slice const&, rocksdb::Slice const&) (in /chain/xtopchain)
|     |                 ->41.07% (83,886,080B) 0xE570E4: rocksdb::WriteBatch::Iterate(rocksdb::WriteBatch::Handler*) const (in /chain/xtopchain)
|     |                   ->41.07% (83,886,080B) 0xE598D5: rocksdb::WriteBatchInternal::InsertInto(rocksdb::WriteThread::WriteGroup&, unsigned long, rocksdb::ColumnFamilyMemTables*, rocksdb::FlushScheduler*, bool, unsigned long, rocksdb::DB*, bool, bool, bool) (in /chain/xtopchain)
|     |                     ->41.07% (83,886,080B) 0xD45AD7: rocksdb::DBImpl::WriteImpl(rocksdb::WriteOptions const&, rocksdb::WriteBatch*, rocksdb::WriteCallback*, unsigned long*, unsigned long, bool, unsigned long*, unsigned long, rocksdb::PreReleaseCallback*) (in /chain/xtopchain)
|     |                       ->28.75% (58,720,256B) 0x1013B9C: rocksdb::WriteCommittedTxn::CommitWithoutPrepareInternal() (in /chain/xtopchain)
|     |                       | ->28.75% (58,720,256B) 0x1013653: rocksdb::PessimisticTransaction::Commit() (in /chain/xtopchain)
|     |                       |   ->28.75% (58,720,256B) 0xF40E17: rocksdb::PessimisticTransactionDB::Put(rocksdb::WriteOptions const&, rocksdb::ColumnFamilyHandle*, rocksdb

能看到内存分配的调用堆栈情况，据此可以看到哪里分配的内存较多。

手册

一般像下面这样调用Valgrind:

1

valgrind program args

这样将在Valgrind使用Memcheck运行程序program(带有参数args)。内存检查执行一系列的内存检查功能，包括检测访问未初始化的内存，已经分配内存的错误使用(两次释放，释放后再访问，等等)并检查内存泄漏。

可用—tool指定使用其它工具：
valgrind --tool=toolname program args

可使用的工具如下：

• cachegrind是一个缓冲模拟器。它可以用来标出你的程序每一行执行的指令数和导致的缓冲不命中数。
• callgrind在cachegrind基础上添加调用追踪。它可以用来得到调用的次数以及每次函数调用的开销。作为对cachegrind的补充，callgrind可以分别标注各个线程，以及程序反汇编输出的每条指令的执行次数以及缓存未命中数。
• helgrind能够发现程序中潜在的条件竞争。
• lackey是一个示例程序，以其为模版可以创建你自己的工具。在程序结束后，它打印出一些基本的关于程序执行统计数据。
• massif是一个堆剖析器，它测量你的程序使用了多少堆内存。
• memcheck是一个细粒度的的内存检查器。
• none没有任何功能。它它一般用于Valgrind的调试和基准测试。

基本选项：
这些选项对所有工具都有效。

-h —help
显示所有选项的帮助，包括内核和选定的工具两者。

—help-debug
和—help相同，并且还能显示通常只有Valgrind的开发人员使用的调试选项。

—version
显示Valgrind内核的版本号。工具可以有他们自已的版本号。这是一种保证工具只在它们可以运行的内核上工作的一种设置。这样可以减少在工具和内核之间版本兼容性导致奇怪问题的概率。

-q —quiet
安静的运行，只打印错误信息。在进行回归测试或者有其它的自动化测试机制时会非常有用。

-v —verbose
显示详细信息。在各个方面显示你的程序的额外信息，例如：共享对象加载，使用的重置，执行引擎和工具的进程，异常行为的警告信息。重复这个标记可以增加详细的级别。

-d 调试Valgrind自身发出的信息。通常只有Valgrind开发人员对此感兴趣。重复这个标记可以产生更详细的输出。如果你希望发送一个bug报告，通过-v -d生成的输出会使你的报告更加有效。

—tool= [default: memcheck]
运行toolname指定的Valgrind，例如，Memcheck, Addrcheck, Cachegrind,等等。

—trace-children= [default: no]
当这个选项打开时，Valgrind会跟踪到子进程中。这经常会导致困惑，而且通常不是你所期望的，所以默认这个选项是关闭的。

—track-fds= [default: no]
当这个选项打开时，Valgrind会在退出时打印一个打开文件描述符的列表。每个文件描述符都会打印出一个文件是在哪里打开的栈回溯，和任何与此文件描述符相关的详细信息比如文件名或socket信息。

—time-stamp= [default: no]
当这个选项打开时，每条信息之前都有一个从程序开始消逝的时间，用天，小时，分钟，秒和毫秒表示。

—log-fd= [default: 2, stderr]
指定Valgrind把它所有的消息都输出到一个指定的文件描述符中去。默认值2,　是标准错误输出(stderr)。注意这可能会干扰到客户端自身对stderr的使用, Valgrind的输出与客户程序的输出将穿插在一起输出到stderr。

—log-file=
指定Valgrind把它所有的信息输出到指定的文件中。实际上，被创建文件的文件名是由filename、’.’和进程号连接起来的（即.），从而每个进程创建不同的文件。

—log-file-exactly=
类似于—log-file，但是后缀”.pid”不会被添加。如果设置了这个选项，使用Valgrind跟踪多个进程，可能会得到一个乱七八糟的文件。

—log-file-qualifier=
当和—log-file一起使用时，日志文件名将通过环境变量$VAR来筛选。这对于MPI程序是有益的。更多的细节，查看手册2.3节 “注解”。

—log-socket=
指定Valgrind输出所有的消息到指定的IP，指定的端口。当使用1500端口时，端口有可能被忽略。如果不能建立一个到指定端口的连接，Valgrind将输出写到标准错误(stderr)。这个选项经常和一个Valgrind监听程序一起使用。

错误相关选项：
这些选项适用于所有产生错误的工具，比如Memcheck,　但是Cachegrind不行。

—xml= [default: no]
当这个选项打开时，输出将是XML格式。这是为了使用Valgrind的输出做为输入的工具，例如GUI前端更加容易些。目前这个选项只在Memcheck时生效。

—xml-user-comment=
在XML开头 附加用户注释，仅在指定了—xml=yes时生效，否则忽略。

—demangle= [default: yes]
打开/关闭C++的名字自动解码。默认打开。当打开时，Valgrind将尝试着把编码过的C++名字自动转回初始状态。这个解码器可以处理g++版本为2.X,3.X或4.X生成的符号。

一个关于名字编码解码重要的事实是，禁止文件中的解码函数名仍然使用他们未解码的形式。Valgrind在搜寻可用的禁止条目时不对函数名解码，因为这将使禁止文件内容依赖于Valgrind的名字解码机制状态， 会使速度变慢，且无意义。

—num-callers= [default: 12]
默认情况下，Valgrind显示12层函数调用的函数名有助于确定程序的位置。可以通过这个选项来改变这个数字。这样有助在嵌套调用的层次很深时确定程序的位置。注意错误信息通常只回溯到最顶上的4个函数。(当前函数，和它的3个调用者的位置)。所以这并不影响报告的错误总数。

这个值的最大值是50。注意高的设置会使Valgrind运行得慢，并且使用更多的内存,但是在嵌套调用层次比较高的程序中非常实用。

—error-limit= [default: yes]
当这个选项打开时，在总量达到10,000,000，或者1,000个不同的错误，Valgrind停止报告错误。这是为了避免错误跟踪机制在错误很多的程序下变成一个巨大的性能负担。

—error-exitcode= [default: 0]
指定如果Valgrind在运行过程中报告任何错误时的退出返回值，有两种情况；当设置为默认值(零)时，Valgrind返回的值将是它模拟运行的程序的返回值。当设置为非零值时，如果Valgrind发现任何错误时则返回这个值。在Valgrind做为一个测试工具套件的部分使用时这将非常有用，因为使测试工具套件只检查Valgrind返回值就可以知道哪些测试用例Valgrind报告了错误。

—show-below-main= [default: no]
默认地，错误时的栈回溯不显示main()之下的任何函数(或者类似的函数像glibc的__libc_start_main()，如果main()没有出现在栈回溯中)；这些大部分都是令人厌倦的C库函数。如果打开这个选项，在main()之下的函数也将会显示。

—suppressions= [default: $PREFIX/lib/valgrind/default.supp]
指定一个额外的文件读取不需要理会的错误；你可以根据需要使用任意多的额外文件。

—gen-suppressions= [default: no]
当设置为yes时，Valgrind将会在每个错误显示之后自动暂停并且打印下面这一行：

1

---- Print suppression ? --- [Return/N/n/Y/y/C/c] ----

这个提示的行为和—db-attach选项(见下面)相同。

如果选择是，Valgrind会打印出一个错误的禁止条目，你可以把它剪切然后粘帖到一个文件，如果不希望在将来再看到这个错误信息。

当设置为all时，Valgrind会对每一个错误打印一条禁止条目，而不向用户询问。

这个选项对C++程序非常有用，它打印出编译器调整过的名字。

注意打印出来的禁止条目是尽可能的特定的。如果需要把类似的条目归纳起来，比如在函数名中添加通配符。并且，有些时候两个不同的错误也会产生同样的禁止条目，这时Valgrind就会输出禁止条目不止一次，但是在禁止条目的文件中只需要一份拷贝(但是如果多于一份也不会引起什么问题)。并且，禁止条目的名字像<在这儿输入一个禁止条目的名字>;名字并不是很重要，它只是和-v选项一起使用打印出所有使用的禁止条目记录。

—db-attach= [default: no]
当这个选项打开时，Valgrind将会在每次打印错误时暂停并打出如下一行：

1

---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ----

按下回车,或者N、回车，n、回车，Valgrind不会对这个错误启动调试器。

按下Y、回车，或者y、回车，Valgrind会启动调试器并设定在程序运行的这个点。当调试结束时，退出，程序会继续运行。在调试器内部尝试继续运行程序，将不会生效。

按下C、回车，或者c、回车，Valgrind不会启动一个调试器，并且不会再次询问。

注意：—db-attach=yes与—trace-children=yes有冲突。你不能同时使用它们。Valgrind在这种情况下不能启动。

—db-command= [default: gdb -nw %f %p]
通过—db-attach指定如何使用调试器。默认的调试器是gdb.默认的选项是一个运行时扩展Valgrind的模板。 %f会用可执行文件的文件名替换，%p会被可执行文件的进程ID替换。

这指定了Valgrind将怎样调用调试器。默认选项不会因为在构造时是否检测到了GDB而改变,通常是/usr/bin/gdb.使用这个命令，你可以指定一些调用其它的调试器来替换。

给出的这个命令字串可以包括一个或多个%p %f扩展。每一个%p实例都被解释成将调试的进程的PID，每一个%f实例都被解释成要调试的进程的可执行文件路径。

—input-fd= [default: 0, stdin]
使用—db-attach=yes和—gen-suppressions=yes选项，在发现错误时，Valgrind会停下来去读取键盘输入。默认地，从标准输入读取，所以关闭了标准输入的程序会有问题。这个选项允许你指定一个文件描述符来替代标准输入读取。

—max-stackframe= [default: 2000000]
栈的最大值。如果栈指针的偏移超过这个数量，Valgrind则会认为程序是切换到了另外一个栈执行。

如果在程序中有大量的栈分配的数组，你可能需要使用这个选项。valgrind保持对程序栈指针的追踪。如果栈指针的偏移超过了这个数量，Valgrind假定你的程序切换到了另外一个栈，并且Memcheck行为与栈指针的偏移没有超出这个数量将会不同。通常这种机制运转得很好。然而，如果你的程序在栈上申请了大的结构，这种机制将会表现得愚蠢，并且Memcheck将会报告大量的非法栈内存访问。这个选项允许把这个阀值设置为其它值。

应该只在Valgrind的调试输出中显示需要这么做时才使用这个选项。在这种情况下，它会告诉你应该指定的新的阀值。

普遍地，在栈中分配大块的内存是一个坏的主意。因为这很容易用光你的栈空间，尤其是在内存受限的系统或者支持大量小堆栈的线程的系统上，因为Memcheck执行的错误检查，对于堆上的数据比对栈上的数据要高效很多。如果你使用这个选项，你可能希望考虑重写代码在堆上分配内存而不是在栈上分配。

MALLOC()相关的选项:
对于使用自有版本的malloc() (例如Memcheck和massif)，下面的选项可以使用。

—alignment= [default: 8]
默认Valgrind的malloc(),realloc(), 等等，是8字节对齐地址的。这是大部分处理器的标准。然而，一些程序可能假定malloc()等总是返回16字节或更多对齐的内存。提供的数值必须在8和4096区间之内，并且必须是2的幂数。

非通用选项：
这些选项可以用于所有的工具，它们影响Valgrind core的几个特性。大部分人不会用到这些选项。

—run-libc-freeres= [default: yes]
GNU C库(libc.so)，所有程序共用的，可能会分配一部分内存自已用。通常在程序退出时释放内存并不麻烦 — 这里没什么问题，因为Linux内核一个进程退出时会回收进程全部的资源，所以这只是会造成速度慢。

glibc的作者认识到这样会导致内存检查器，像Valgrind，在退出时检查内存错误的报告glibc的内存泄漏问题，为了避免这个问题，他们提供了一个__libc_freeres()例程特别用来让glibc释放分配的所有内存。因此Memcheck在退出时尝试着去运行__libc_freeres()。

不幸的是，在glibc的一些版本中，libc_freeres是有bug会导致段错误的。这在Red Hat 7.1上有特别声明。所以，提供这个选项来决定是否运行libc_freeres。如果你的程序看起来在Valgrind上运行得很好，但是在退出时发生段错误，你可能需要指定—run-libc-freeres=no来修正，这将可能错误的报告libc.so的内存泄漏。

—sim-hints=hint1,hint2,…
传递杂凑的提示给Valgrind，轻微的修改模拟行为的非标准或危险方式，可能有助于模拟奇怪的特性。默认没有提示打开。小心使用！目前已知的提示有：

• lax-ioctls: 对ioctl的处理非常不严格，唯一的假定是大小是正确的。不需要在写时缓冲区完全的初始化。没有这个，用大量的奇怪的ioctl命令来使用一些设备驱动将会非常烦人。
• enable-inner:打开某些特殊的效果，当运行的程序是Valgrind自身时。

—kernel-variant=variant1,variant2,…
处理系统调用和ioctls在这个平台的默认核心上产生不同的变量。这有助于运行在改进过的内核或者支持非标准的ioctls上。小心使用。如果你不理解这个选项做的是什么那你几乎不需要它。已经知道的变量有：

• bproc: 支持X86平台上的sys_broc系统调用。这是为了运行在BProc，它是标准Linux的一个变种，有时用来构建集群。

—show-emwarns= [default: no]
当这个选项打开时，Valgrind在一些特定的情况下将对CPU仿真产生警告。通常这些都是不引人注意的。

—smc-check= [default: stack]
这个选项控制Valgrind对自我修改的代码的检测。Valgrind可以不做检测，可以检测栈中自我修改的代码，或者任意地方检测自我修改的代码。注意默认选项是捕捉绝大多数情况，到目前我们了解的情况为止。使用all选项时会极大的降低速度。(但是用none选项运行极少影响速度，因为对大多数程序，非常少的代码被添加到栈中)

调试VALGRIND选项：
还有一些选项是用来调试Valgrind自身的。在运行一般的东西时不应该需要的。如果你希望看到选项列表，使用—help-debug选项。

内存检查选项：
—leak-check= [default: summary]
当这个选项打开时，当客户程序结束时查找内存泄漏。内存泄漏意味着有用malloc分配内存块，但是没有用free释放，而且没有指针指向这块内存。这样的内存块永远不能被程序释放，因为没有指针指向它们。如果设置为summary，Valgrind会报告有多少内存泄漏发生了。如果设置为full或yes，Valgrind给出每一个独立的泄漏的详细信息。

—show-reachable= [default: no]
当这个选项关闭时，内存泄漏检测器只显示没有指针指向的内存块，或者只能找到指向块中间的指针。当这个选项打开时，内存泄漏检测器还报告有指针指向的内存块。这些块是最有可能出现内存泄漏的地方。你的程序可能，至少在原则上，应该在退出前释放这些内存块。这些有指针指向的内存块和没有指针指向的内存块，或者只有内部指针指向的块，都可能产生内存泄漏，因为实际上没有一个指向块起始的指针可以拿来释放，即使你想去释放它。

—leak-resolution= [default: low]
在做内存泄漏检查时，确定memcheck将怎么样考虑不同的栈是相同的情况。当设置为low时，只需要前两层栈匹配就认为是相同的情况；当设置为med，必须要四层栈匹配，当设置为high时，所有层次的栈都必须匹配。

对于hardcore内存泄漏检查，你很可能需要使用—leak-resolution=high和—num-callers=40或者更大的数字。注意这将产生巨量的信息，这就是为什么默认选项是四个调用者匹配和低分辨率的匹配。注意—leak-resolution= 设置并不影响memcheck查找内存泄漏的能力。它只是改变了结果如何输出。

—freelist-vol= [default: 5000000]
当客户程序使用free(C中)或者delete(C++)释放内存时，这些内存并不是马上就可以用来再分配的。这些内存将被标记为不可访问的，并被放到一个已释放内存的队列中。这样做的目的是，使释放的内存再次被利用的点尽可能的晚。这有利于memcheck在内存块释放后这段重要的时间检查对块不合法的访问。

这个选项指定了队列所能容纳的内存总容量，以字节为单位。默认的值是5000000字节。增大这个数目会增加memcheck使用的内存，但同时也增加了对已释放内存的非法使用的检测概率。

—workaround-gcc296-bugs= [default: no]
当这个选项打开时，假定读写栈指针以下的一小段距离是gcc 2.96的bug，并且不报告为错误。距离默认为256字节。注意gcc 2.96是一些比较老的Linux发行版(RedHat 7.X)的默认编译器，所以你可能需要使用这个选项。如果不是必要请不要使用这个选项，它可能会使一些真正的错误溜掉。一个更好的解决办法是使用较新的，修正了这个bug的gcc/g++版本。

—partial-loads-ok= [default: no]
控制memcheck如何处理从地址读取时字长度，字对齐，因此哪些字节是可以寻址的，哪些是不可以寻址的。当设置为yes是，这样的读取并不抛出一个寻址错误。而是从非法地址读取的V字节显示为未定义，访问合法地址仍然是像平常一样映射到内存。

设置为no时，从部分错误的地址读取与从完全错误的地址读取同样处理：抛出一个非法地址错误，结果的V字节显示为合法数据。

注意这种代码行为是违背ISO C/C++标准，应该被认为是有问题的。如果可能，这种代码应该修正。这个选项应该只是做为一个最后考虑的方法。

—undef-value-errors= [default: yes]
控制memcheck是否检查未定义值的危险使用。当设为yes时，Memcheck的行为像Addrcheck, 一个轻量级的内存检查工具，是Valgrind的一个部分，它并不检查未定义值的错误。使用这个选项，如果你不希望看到未定义值错误。

CACHEGRIND选项：
手动指定I1/D1/L2缓冲配置，大小是用字节表示的。这三个必须用逗号隔开，中间没有空格，例如：

1

valgrind --tool=cachegrind --I1=65535,2,64

你可以指定一个，两个或三个I1/D1/L2缓冲。如果没有手动指定，每个级别使用
普通方式(通过CPUID指令得到缓冲配置，如果失败，使用默认值)得到的配置。

—I1=,,
指定第一级指令缓冲的大小，关联度和行大小。

—D1=,,
指定第一级数据缓冲的大小，关联度和行大小。

—L2=,,
指定第二级缓冲的大小，关联度和行大小。

CALLGRIND选项：

—heap= [default: yes]
当这个选项打开时，详细的追踪堆的使用情况。关闭这个选项时，massif.pid.txt或massif.pid.html将会非常的简短。

—heap-admin= [default: 8]
每个块使用的管理字节数。这只能使用一个平均的估计值，因为它可能变化。glibc使用的分配器每块需要4~15字节，依赖于各方面的因素。管理已经释放的块也需要空间，尽管massif不计算这些。

—stacks= [default: yes]
当打开时，在剖析信息中包含栈信息。多线程的程序可能有多个栈。

—depth= [default: 3]
详细的堆信息中调用过程的深度。增加这个值可以给出更多的信息，但是massif会更使这个程序运行得慢，使用更多的内存，并且产生一个大的massif.pid.txt或者massif.pid.hp文件。

—alloc-fn=
指定一个分配内存的函数。这对于使用malloc()的包装函数是有用的，可以用它来填充原来无效的上下文信息。(这些函数会给出无用的上下文信息，并在图中给出无意义的区域)。指定的函数在上下文中被忽略，例如，像对malloc()一样处理。这个选项可以在命令行中重复多次，指定多个函数。

—format= [default: text]
产生text或者HTML格式的详细堆信息，文件的后缀名使用.txt或者.html。

HELGRIND选项：

—private-stacks= [default: no]
假定线程栈是私有的。

—show-last-access= [default: no]
显示最后一次字访问出错的位置。

LACKEY选项：
—fnname= [default: _dl_runtime_resolve()]
对函数计数。

—detailed-counts= [default: no]
对读取，存储和alu操作计数。

利用GCC编译选项Sanitizers快速定位内存错误

先从一个小例子开头

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

#include<iostream>
using namespace std;
 
int main(int argc, char **argv) {
  int *array = new int[100];
  delete [] array;
  array[argc]==1;  //can't detected
  cout&lt;&lt; "passed 1st"&lt;&lt;endl;
 
  array[argc] = array[argc];
  cout&lt;&lt; "passed 2nd"&lt;&lt;endl;
 
  array[argc]=100;  // BOOM
  cout&lt;&lt;"passed 3rd"&lt;&lt;endl;
}

1
2

$ g++ -g -O -fsanitize=address -o asan heap-use-after-free.cpp
$ ./asan

重点在这个-fsanitize=address选项上，不加它运行这段代码基本是不会报错的。

Sanitizers简介

Sanitizers是谷歌发起的开源工具集，包括了AddressSanitizer，MemorySanitizer，ThreadSanitizer，LeakSanitizer，Sanitizers项目本是LLVM项目的一部分，但GNU也将该系列工具加入到了自家的GCC编译器中。GCC从4.8版本开始支持Address和Thread Sanitizer，4.9版本开始支持Leak Sanitizer和UB Sanitizer，这些都是查找隐藏Bug的利器。

Enable AddressSanitizer, a fast memory error detector. Memory access instructions are instrumented to detect out-of-bounds and use-after-free bugs. The option enables -fsanitize-address-use-after-scope. See https://github.com/google/sanitizers/wiki/AddressSanitizer for more details. The run-time behavior can be influenced using the ASAN_OPTIONS environment variable. When set to help=1, the available options are shown at startup of the instrumented program. See https://github.com/google/sanitizers/wiki/AddressSanitizerFlags#run-time-flags for a list of supported options. The option cannot be combined with -fsanitize=thread and/or -fcheck-pointer-bounds.

-fsanitize=kernel-address：
Enable AddressSanitizer for Linux kernel. See https://github.com/google/kasan/wiki for more details. The option cannot be combined with -fcheck-pointer-bounds.

-fsanitize=thread：
Enable ThreadSanitizer, a fast data race detector. Memory access instructions are instrumented to detect data race bugs. See https://github.com/google/sanitizers/wiki#threadsanitizer for more details. The run-time behavior can be influenced using the TSAN_OPTIONS environment variable; see https://github.com/google/sanitizers/wiki/ThreadSanitizerFlags for a list of supported options. The option cannot be combined with -fsanitize=address, -fsanitize=leak and/or -fcheck-pointer-bounds.

Note that sanitized atomic builtins cannot throw exceptions when operating on invalid memory addresses with non-call exceptions (-fnon-call-exceptions).

-fsanitize=leak：
Enable LeakSanitizer, a memory leak detector. This option only matters for linking of executables and the executable is linked against a library that overrides malloc and other allocator functions. See https://github.com/google/sanitizers/wiki/AddressSanitizerLeakSanitizer for more details. The run-time behavior can be influenced using the LSAN_OPTIONS environment variable. The option cannot be combined with -fsanitize=thread.

-fsanitize=undefined：
Enable UndefinedBehaviorSanitizer, a fast undefined behavior detector. Various computations are instrumented to detect undefined behavior at runtime. Current suboptions are:

-fsanitize=shift：
This option enables checking that the result of a shift operation is not undefined. Note that what exactly is considered undefined differs slightly between C and C++, as well as between ISO C90 and C99, etc. This option has two suboptions, -fsanitize=shift-base and -fsanitize=shift-exponent.

-fsanitize=shift-exponent：
This option enables checking that the second argument of a shift operation is not negative and is smaller than the precision of the promoted first argument.

-fsanitize=shift-base：
If the second argument of a shift operation is within range, check that the result of a shift operation is not undefined. Note that what exactly is considered undefined differs slightly between C and C++, as well as between ISO C90 and C99, etc.

-fsanitize=integer-divide-by-zero：
Detect integer division by zero as well as INT_MIN / -1 division.

-fsanitize=unreachable：
With this option, the compiler turns the builtin_unreachable call into a diagnostics message call instead. When reaching the builtin_unreachable call, the behavior is undefined.

-fsanitize=vla-bound：
This option instructs the compiler to check that the size of a variable length array is positive.

-fsanitize=null：
This option enables pointer checking. Particularly, the application built with this option turned on will issue an error message when it tries to dereference a NULL pointer, or if a reference (possibly an rvalue reference) is bound to a NULL pointer, or if a method is invoked on an object pointed by a NULL pointer.

-fsanitize=return：
This option enables return statement checking. Programs built with this option turned on will issue an error message when the end of a non-void function is reached without actually returning a value. This option works in C++ only.

-fsanitize=signed-integer-overflow：
This option enables signed integer overflow checking. We check that the result of +, *, and both unary and binary – does not overflow in the signed arithmetics. Note, integer promotion rules must be taken into account. That is, the following is not an overflow:

1
2

signed char a = SCHAR_MAX;
a++;

-fsanitize=bounds：
This option enables instrumentation of array bounds. Various out of bounds accesses are detected. Flexible array members, flexible array member-like arrays, and initializers of variables with static storage are not instrumented. The option cannot be combined with -fcheck-pointer-bounds.

-fsanitize=bounds-strict：
This option enables strict instrumentation of array bounds. Most out of bounds accesses are detected, including flexible array members and flexible array member-like arrays. Initializers of variables with static storage are not instrumented. The option cannot be combined with -fcheck-pointer-bounds.

-fsanitize=alignment：
This option enables checking of alignment of pointers when they are dereferenced, or when a reference is bound to insufficiently aligned target, or when a method or constructor is invoked on insufficiently aligned object.

-fsanitize=object-size：
This option enables instrumentation of memory references using the __builtin_object_size function. Various out of bounds pointer accesses are detected.

-fsanitize=float-divide-by-zero：
Detect floating-point division by zero. Unlike other similar options, -fsanitize=float-divide-by-zero is not enabled by -fsanitize=undefined, since floating-point division by zero can be a legitimate way of obtaining infinities and NaNs.

-fsanitize=float-cast-overflow：
This option enables floating-point type to integer conversion checking. We check that the result of the conversion does not overflow. Unlike other similar options, -fsanitize=float-cast-overflow is not enabled by -fsanitize=undefined. This option does not work well with FE_INVALID exceptions enabled.

-fsanitize=nonnull-attribute：
This option enables instrumentation of calls, checking whether null values are not passed to arguments marked as requiring a non-null value by the nonnull function attribute.

-fsanitize=returns-nonnull-attribute：
This option enables instrumentation of return statements in functions marked with returns_nonnull function attribute, to detect returning of null values from such functions.

-fsanitize=bool：
This option enables instrumentation of loads from bool. If a value other than 0/1 is loaded, a run-time error is issued.

-fsanitize=enum：
This option enables instrumentation of loads from an enum type. If a value outside the range of values for the enum type is loaded, a run-time error is issued.

-fsanitize=vptr：
This option enables instrumentation of C++ member function calls, member accesses and some conversions between pointers to base and derived classes, to verify the referenced object has the correct dynamic type.

While -ftrapv causes traps for signed overflows to be emitted, -fsanitize=undefined gives a diagnostic message. This currently works only for the C family of languages.

-fno-sanitize=all：
This option disables all previously enabled sanitizers. -fsanitize=all is not allowed, as some sanitizers cannot be used together.

-fasan-shadow-offset=number：
This option forces GCC to use custom shadow offset in AddressSanitizer checks. It is useful for experimenting with different shadow memory layouts in Kernel AddressSanitizer.

-fsanitize-sections=s1,s2,…：
Sanitize global variables in selected user-defined sections. si may contain wildcards.

-fsanitize-recover[=opts]：
-fsanitize-recover= controls error recovery mode for sanitizers mentioned in comma-separated list of opts. Enabling this option for a sanitizer component causes it to attempt to continue running the program as if no error happened. This means multiple runtime errors can be reported in a single program run, and the exit code of the program may indicate success even when errors have been reported. The -fno-sanitize-recover= option can be used to alter this behavior: only the first detected error is reported and program then exits with a non-zero exit code.

Currently this feature only works for -fsanitize=undefined (and its suboptions except for -fsanitize=unreachable and -fsanitize=return), -fsanitize=float-cast-overflow, -fsanitize=float-divide-by-zero, -fsanitize=bounds-strict, -fsanitize=kernel-address and -fsanitize=address. For these sanitizers error recovery is turned on by default, except -fsanitize=address, for which this feature is experimental. -fsanitize-recover=all and -fno-sanitize-recover=all is also accepted, the former enables recovery for all sanitizers that support it, the latter disables recovery for all sanitizers that support it.

Even if a recovery mode is turned on the compiler side, it needs to be also enabled on the runtime library side, otherwise the failures are still fatal. The runtime library defaults to halt_on_error=0 for ThreadSanitizer and UndefinedBehaviorSanitizer, while default value for AddressSanitizer is halt_on_error=1. This can be overridden through setting the halt_on_error flag in the corresponding environment variable.

Syntax without an explicit opts parameter is deprecated. It is equivalent to specifying an opts list of:

undefined,float-cast-overflow,float-divide-by-zero,bounds-strict

-fsanitize-address-use-after-scope：
Enable sanitization of local variables to detect use-after-scope bugs. The option sets -fstack-reuse to ‘none’.

-fsanitize-undefined-trap-on-error：
The -fsanitize-undefined-trap-on-error option instructs the compiler to report undefined behavior using __builtin_trap rather than a libubsan library routine. The advantage of this is that the libubsan library is not needed and is not linked in, so this is usable even in freestanding environments.

-fsanitize-coverage=trace-pc：
Enable coverage-guided fuzzing code instrumentation. Inserts a call to __sanitizer_cov_trace_pc into every basic block

内核同步

内核为不同的请求服务

内核抢占

如果进程正在执行内核函数时，即在内核态运行，允许发生内核切换，这个内核就是抢占的。

无论在抢占还是非抢占内核中，运行在内核态的进程都可以自动放弃CPU，这叫做计划性进程切换。抢占式内核在响应引起进程切换的异步事件的方式上与非抢占内核有差别，叫做强制性进程切换。所有的切换都是由宏switch_to实现的。

抢占式内核的特点是一个在内核态运行的进程，可能在执行内核函数期间被另一个进程取代。使内核可抢占的目的是减少用户态进程的分派延迟，即从进程变为可执行状态到他实际开始运行之间的时间间隔。当被current_thread_info()宏所引用的thread_info描述符的preempt_count字段大于0的时候就禁止内核抢占，该字段的编码对应三个不同的计数器，因此它在如下几种情况时都大于0：

• 内核正在执行中断服务例程
• 可延迟函数被禁止
• 通过把抢占计数器设置为正数而显式的禁用内核调用

因此只有当内核正在执行异常处理程序，而且内核抢占没有被显式禁用，才可能抢占内核。表中列出了一些简单的宏，它们处理preempt_count字段的抢占计数器。

preempt_enable()宏递减抢占计数器，检查TIF_NEED_RESCHED是否被设置。此时，进程切换请求是挂起的，因此调用preempt_schedule()函数：

1
2
3
4
5
6

// 检查 preempt_count 是否为0，以及是否允许本地中断
if(!current_thread_info->preempt_count && !irqs_disabled()){
	current_thread_info->preempt_count = PREMPT_ACTIVE;
	schedule();   // 选择另外一个进程运行
	current_thread_info->preempt_count = 0;
}

该函数检查是否允许本地中断，以及当前进程的preempt_count字段是否为0，如果两个条件都为真，就调用schedule()选择另一个进程来运行。内核抢占可能在结束内核控制路径时发生，也可能在异常处理程序调用preempt_enable()时发生。

什么时候同步是必需的

当计算结果依赖于两个或两个以上的交叉内核控制路径的嵌套方式时，可能出现竞争条件。临界区是一段代码，在其他的内核控制路径能进入临界区前，进入临界区的内核控制路径必须执行完这段代码。

什么时候同步是不必要的

• 中断处理程序和 tasklet 不必编写成可重入的函数。
• 仅被软中断和 tasklet 访问的 每 CPU 变量不需要同步。
• 仅被一种 tasklet 访问发数据结构不需要同步。

同步原语

表中列出了Linux内核使用的同步技术。

每 CPU 变量

最简单的同步技术包括把内核变量声明为每CPU变量，主要是一个数组，系统中的每个 CPU 对应数组的一个元素。一个 CPU 不应访问其他 CPU 对应的数组元素，另外，它可以随意修改它自己的元素而不用担心出现竞争条件。这意味着它只能在确定系统的CPU上的数据在逻辑上是独立的时候才能使用。

虽然每 CPU 变量为来自不同 CPU 的并发访问提供包含，但对来自异步函数（中断处理程序和可延迟函数）的访问不提供保护，这需要另外的同步原语。此外，在单处理器和多处理器系统中内核抢占都可能使每CPU变量产生竞争条件。总的原则是内核控制路径应该在禁用抢占的情况下访问每CPU变量。

原子操作

避免由于“读——修改——写”指令引起的竞争条件的最容易的办法，就是确保这样的操作在芯片级是原子的。任何一个这样的操作都必须以单个指令执行，中间不能中断，且避免其他的CPU访问同一存储器单元。这些很小的原子操作（atomic operations）可以建立在其他更灵活机制的基础之上以创建临界区。

回顾一下80x86的指令；

• 进行零次或一次对齐内存访问的汇编指令是原子的
• 如果在读操作之后、写操作之前没有其他处理器占用内存总线，那么从内存中读取数据、更新数据并把更新后的数据写回内存中的这些“读——修改——写”汇编语言指令（例如inc或dec)是原子的。当然，在单处理器系统中，永远都不会发生内存总线窃用的情况。
• 操作码前缀是lock字节(0xf0)的“读——修改——写”汇编语言指令即使在多处理器系统中也是原子的。当控制单元检测到这个前缀时，就“锁定”内存总线，直到这条指令执行完成为止。因此，当加锁的指令执行时，其他处理器不能访问这个内存单元。
• 操作码前缀是一个rep字节（0xf2，0xf3)的汇编语言指令不是原子的，这条指令强行让控制单元多次重复执行相同的指令。控制单元在执行新的循环之前要检查挂起的中断。

Linux提供了atmoic_t类型和专门的函数和宏，作用于atmoic_t变量，并当作单独的原子的汇编指令来使用。

另一类原子函数操作作用于位掩码

优化和内存屏障

编译器可能重新安排汇编语言指令以使寄存器以最优方式使用，此外现代CPU通常并行地执行若干条指令，且可重新安排内存访问。优化屏障原语保证编译程序不会混淆放在原语操作之前的汇编指令和放在原语操作之后的汇编语言指令。Linux 中，优化屏障是barrier()宏，展开为asm volatile("":::“memory”)。volatile禁止编译器把asm指令与程序中的其他指令重新组合，memory关键字强制编译器假定RAM中的所有内存单元已被汇编指令修改，因此编译器不能使用存放在CPU寄存器中的内存单元来优化asm指令前的代码。

内存屏障原语确保在原语执行之后的操作执行之前，原语前的操作已经完成。下列指令是串行的，因为它们起内存屏障的作用：

• 对IO端口进行操作的指令
• 有lock前缀的所有指令
• 写控制寄存器、系统寄存器或调试寄存器的所有指令（例如cli和sti，用于修改eflags寄存器的IF标志的状态）
• 引入的汇编语言指令lfence、sfence和mfence，它们分别有效地实现读内存屏障、写内存屏障和读写内存屏障。

Linux使用6个内存屏障原语：

内存屏障原语的实现依赖于体系结构，如果CPU支持lfence指令，就把rmb()展开为asm volatile("lfence")，否则展开为asm volatile("lock;addl $0,0(%%esp)":::"memory")。asm告诉编译器插入一些汇编指令并起到优化屏障的作用，lock;addl $0,0(%%esp)把0加到栈顶的内存单元，这条指令本身没有价值，但是lock前缀使得这条指令成为CPU的内存屏障。

Intel的wmb()宏更简单，因为它展开为barrier()，因为Intel从不对写内存访问重新排序。

自旋锁

当内核控制路径必须访问共享数据结构或进入临界区时，就需要为自己获取一把“锁”。自旋锁时用来在多处理器环境中工作的一种特殊的锁。如果内核控制路径发现锁被运行在另一个 CPU 上的内核控制路径“锁着”，就会在周围“旋转”，反复执行一条紧凑的循环指令（“忙等”），直到锁被释放。自旋锁的循环指令表示忙等，即使等待的CPU无事可做也会占用CPU。

一般来说，有自旋锁保护的每个临界区都是禁止内核抢占的。在单处理器上自旋锁本身不起作用，只是禁止或启用内核抢占。等待自旋锁释放的进程可能被更高优先级的进程替代。

Linux中的自旋锁用spinlock_t表示：

• slock，自旋锁的状态，1：未加锁；<=0：加锁。
• break_slock，进程正在忙等自旋锁。

六个宏用于初始化、设置、测试自旋锁，所有的宏都是基于原子操作的，保证自旋锁在多个CPU都想修改自旋锁时也能正确更新。

具有内核抢占的 spin_lock 宏

用于请求自旋锁的spin_lock宏：

• 调用preempt_disable()禁用内核抢占

• _raw_spin_trylock()对自旋锁的 slock 字段执行原子性的测试和设置操作。

  • 函数首先执行指令如下，

    1 2	movb $0, %al xchgb %al, slp->slock // xchg 原子性地交换 8 位寄存器 %al 和 slp->slock

• 如果自旋锁中的旧值是正数，宏结束：内核控制路径已经获得自旋锁

• 否则，内核控制路径无法获得自旋锁，宏必须执行循环一直到在其他CPU上运行的内核控制路径释放自旋锁。调用preempt_enable()递减在第 1 步 递增了的抢占计数器。忙等期间可被其他进程抢占。
• 如果break_lock字段等于 0，则设置为 1。通过检测该字段，拥有锁且在别的 CPU 上运行的进程就能知道是否有其他进程在等待该锁。如果进程持有某个自旋锁的时间过长，该进程可提前释放锁。

• 执行等待循环：

  1 2	while(spin_is_locked(slp) && slp->break_lock) cpu_relax(); // 宏 cpu_relax() 简化为一条 pause 汇编指令，引入很短的延迟，加快了紧跟在锁后边的代码的执行并减少了能源消耗。

• 回到第 1 步，再次试图获取自旋锁。

非抢占式内核中的 spin_lock 宏

如果在内核编译时没有旋转内核抢占选项，spin_lock 宏本质上为：

1
2
3
4
5
6
7

1: lock; decb slp->slock  // decb 递减自旋锁的值，该指令是原子的，因为带有 lock 前缀
   jns 3f  // 检测符号标志，如果被清 0，说明自旋锁被设置为 1（未锁），从 3 处继续执行，f：forward
2: pause   // 否则，在 2 处执行紧凑的循环，直到自旋锁出现正值
   cmpb $0, slp->slock
   jle 2b
   jmp 1b  // 然后从 1 处重新执行，检查是否其他的处理器抢占了锁
3: 

spin_unlock 宏

spin_unlock宏释放以前获得的自旋锁，本质上是：

1

movb $1, slp->slock

读/写自旋锁

读/写自旋锁是为了增加内核的并发能力。只要没有内核控制路径对数据结构修改，读/写自旋锁就允许多个内核控制路径同时读同一个数据结构。如果一个内核控制路径想对数据结构进行写操作，必须首先获得读/写锁的写锁，写锁授权独占访问这个资源。

读/写锁是一个rwlock_t结构，lock字段是一个 32 位的字段，分两部分：

• 0~23 位，计数器，对受保护的数据结构并发进行读操作的内核控制路径的数目。
• 第 24 位，“未锁”标志字段，当没有内核控制路径在读或写时设置该位，否则清 0。

lock 值：

• 0x01000000：自旋锁为空（设置了“未锁”标志，且无读者）。
• 0x00000000：写者获得了自旋锁（“未锁”标志清 0，且无读者）。
• 0x00ffffff，0x00fffffe 等：一个或多个读者获得了自旋锁（“未锁”标志清 0，读者个数的二进制补码在 0~23 位上）。

rwlock_t结构也包括break_lock字段。rwlock_init宏把读/写自旋锁的lock字段初始化为 0x01000000（“未锁”)，把break_lock初始化为 0。

读自旋锁

read_lock宏，作用于读/写自旋锁的地址rwlp，与spin_lock相似。如果编译内核时选择了内核抢占选项，read_lock与spin_lock只有一点不同：执行_raw_read_trylock()，在第 2 步获得读/写自旋锁。

1
2
3
4
5
6
7
8
9

int _raw_read_trylock(rwlock_t  *lock)
{
	atomic_t *count = (atomic_t *)lock->lock;
	atomic_dec(count);
	if(atomic_read(count) >= 0)
		return 1;
	atomic_inc(count);
	return 0;
}

读写锁计数器lock是通过原子操作来访问的，但整个函数对计数器的操作并不是原子性的。

如果编译内核时没有选择内核抢占选项，read_lock宏产生如下汇编代码

1
2
3
4
5

	movl $rwlp->lock, %eax
	lock; subl $1, (%eax)    // 将自旋锁原子减 1，增加读者个数
	jns 1f                   // 如果递减操作结果非负，就获得自旋锁    
	call __read_lock_failed  // 否则，调用 __read_lock_failed()
1: 

这里__read_lock_failed()是下列汇编语言函数：

1
2
3
4
5
6
7
8
9

// 试图获取自旋锁
__read_lock_failed:
	lock; incl (%eax)   // 原子增加 lock 字段，以取消 read_lock 宏执行的递减操作
1: 	pause   
	cmpl $1, (%eax)     // 循环，直到 lock 字段 >= 0
	js 1b
	lock; decl (%eax)
	js __read_lock_failed
	ret

read_lock宏原子地把自旋锁的值减一，由此增加读者的个数，如果递减操作产生一个非负值，则获得自旋锁，否则调用__read_lock_failed()，该函数原子性地增加lock字段以取消由read_lock宏执行的递减操作，然后循环直到lock字段变为正数。

read_unlock释放读自旋锁：增加lock字段的计数器，以减少读者的计数，然后调用preempt_enable()重新启用内核抢占。

1

lock; incl rwlp->lock    // 减少读者计数

写自旋锁

write_lock宏与spin_lock()和read_lock()相似。如果支持内核抢占，则禁用内核抢占并调用_raw_write_trylock()获得锁。如果函数返回0，说明锁已被占用，因此忙等待循环。

1
2
3
4
5
6
7
8

int _raw_write_trylock(rwlock_t *lock)
{
	atomic_t *count = (atomic_t *)lock->lock;
	if(atomic_sub_and_test(0x01000000, count))  // 从读/写自旋锁中减去 0x01000000，清除未上锁标志并返回 1
		return 1;
	atomic_add(0x01000000, count);  // 原子地在自旋锁值上增加 0x0100000，以抵消减操作。
	return 0;                       // 锁已经被占用，需重新启用内核抢占并开始忙等待
}

write_unlock宏释放写锁:

1

lock; addl $0x0100000, rwlp  // 把 lock 字段中的“未锁”标识置位

顺序锁

顺序锁与读/写锁相似，只是为写者赋予了较高的优先级：读者读的时候允许写者运行。好处是写者永远不会等待（除非另一个写者在写），缺点是读者有时需多次读相同的数据直到获得有效的副本。

seqlock_t包括两个字段：

• 类型为spinlock_t的lock字段。
• 整型的sequence字段，是一个顺序计数器。每个读者都必须在读数据前后两次读顺序计数器，如果两次读到的值不同，说明新的写者开始写并增加了顺序计数器，读取的数据无效。

将SEQLOCK_UNLOCKED赋给变量seqlock_t，或执行seqlock_init宏，将seqlock_t初始化为未上锁。写者通过调用write_seqlock()和write_sequnlock()获取和释放顺序锁。write_seqlock()获取seqlock_t中的自旋锁，然后使顺序计数器加 1。write_sequnlock()再次增加顺序计数器，然后释放自旋锁。可保证有写者写时，计数器值为奇数，没有写者时，计数器值是偶数。

读者执行下面临界区代码：

1
2
3
4
5
6

unsigned int seq;
do
{
	seq = read_seqbegin(&seqlock);    // 返回顺序锁的当前序号。如果是奇数，或 seq 的值与顺序锁的顺序计数器值不匹配，read_deqretry() 返回 1
	/* ... 临界区 ... */
}while(read_deqretry(&seqlock, seq));

读者进入临界区，不必禁用内核抢占。由于写者获取自旋锁，它进入临界区时自动禁用内核抢占。

使用顺序锁的条件：

• 被保护的数据结构不包括被写者修改和被读者间接引用的指针。
• 读者的临界区代码没有副作用。
• 另外：
  • 读者的临界区代码应该简短。
  • 写者不应常获取顺序锁。

典型例子：保护与系统时间处理相关的数据结构。

读-拷贝-更新（RCU)

是为了保护在多数情况下被多个 CPU 读的数据结构而设计的一种同步技术。RCU 允许多个读者和写者并发执行，且不使用锁，相比读/写自旋锁、顺序锁有更大的优势。通过限制 RCP 的范围，可不使用共享数据结构而实现多个 CPU 同步：

• RCU 只包含被动态分配并通过引用指针引用的数据结构。
• 在被 RCU 保护的临界区中，任何内核控制路径不能睡眠。

内核控制路径读取被 RCU 保护的数据结构流程：

• 执行rcu_read_lock()等同于preempt_disable()。
• 读者间接引用该数据结构指针所对应的内存单元，并开始读该数据结构。读者在完成读操作前，不能睡眠。
• rcu_read_unlock()等同于preempt_enable()，标记临界区的结束。

内核控制路径写被 RCU 保护的数据结构时，需要做一些事情防止竞争条件的出现。

• 写者要更新数据结构时，间接引用指针并生成整个数据结构的副本。
• 写者修改该副本。
• 修改完毕，写者改变指向数据结构的指针，使其指向被修改后的副本。
  • 修改指针的操作是一个原子操作。
  • 需要内存屏障保证：只有数结构被修改后，已更新的指针对其他 CPU 才是可见的。如果把自旋锁与 RCU 结合以禁止写者的并发执行，就隐含地引入了内存屏障。

使用 RCU 技术的困难：写者修改指针时不能立即释放数据结构的旧副本。写着开始修改时，正在访问数据结构的读者可能还在读旧副本。只有 CPU 上所有的读者都执行完宏rcu_read_unlock()后，才能释放旧副本。内核要求每个读者在执行以下操作前执行rcu_read_unlock()宏：

• CPU 执行进程切换。
• CPU 开始在用户态执行。
• CPU 执行空循环。

对于以上任何情况中，认为 CPU 经过了静止状态。

写者调用call_rcu()释放数据结构的旧副本。当所有的CPU都通过静止状态之后，call_rcu()接受rcu_head描述符的地址和将要调用的回调函数的地址作为参数。一旦回调函数被执行，它通常释放数据结构的旧副本。

函数call_rcu()把回调函数和其参数的地址存放在rcu_head描述符中，然后把描述符插入回调函数的每 CPU 链表中，内核每经过一个时钟滴答检查本地 CPU 是否经历了一个静止状态。如果所有 CPU 都经历了静止状态，本地 tasklet 执行链表中的所有回调函数。

信号量

实现了一个加锁原语，即让等待者睡眠，直到等待的资源变为空闲。

Linux 提供两种信号量：

• 内核信号量，由内核控制路径使用。
• System V IPC 信号量，由用户态进程使用。

内核信号量类似自旋锁，当锁关闭时，不允许内核控制路径继续进行。内核控制路径试图获取内核信号量保护的资源时，相应的资源会被挂起，直到资源被释放。因此，只有可睡眠的函数才能获取内核信号量，中断处理程序和可延迟函数不能使用内核信号量。

内核信号量数据结构struct semaphore，包含的字段：

• count，存放atomic_t类型的值。> 0，资源空闲；= 0，信号量忙，但没有进程等待；< 0，资源不可用，至少一个进程等待资源。
• wait，存放等待队列链表的地址，等待该资源的所有睡眠进程都在这个链表中。
• sleepers，表示是否有一些进程在信号量上睡眠。

初始化信号量的几种情形：init_MUTEX()将 count 字段设置为 1（资源空闲），init_MUTEX_LOCKED()将 count 字段设置为 0。宏DECLARE_MUTEX和DECLARE_MUTEX_LOCKED完成同样的功能，但它们也静态分配semaphore结构的变量。将 count 初始化为任意的正整数 n 时，最多有 n 个进程可以并发地访问该资源。

释放信号量

释放内核信号量时，调用up()函数，等价于：

1
2
3
4
5
6
7
8
9
10

	movl $sem->count, %ecx  
	lock; incl (%ecx)
	jg 1f
	lea %ecx, %eax
	pushl %edx
	pushl %ecx
	call __up   // 从 eax 寄存器接收参数
	popl %ecx
	popl %edx
1: 

up()增加*sem信号量 count 字段的值，然后检查它的值是否大于0。如果大于 0，说明没有进程在等待队列上睡眠，什么也不做，否则，调用 __up() 唤醒睡眠的进程。注意__up()从eax寄存器接收参数。__up()是：

1
2
3
4

__attribute_((regparm(3))) void __up(struct semaphore *sem)
{
	wake_up(&sem->wait);
}

获取信号量时需要调用down()函数，等价于：

1
2
3
4
5
6
7
8
9
10
11

down:
	movl $sem->count, %ecx
	lock; decl (%ecx);
	jns 1f
	lea %ecx, %eax
	pushl %edx
	pushl %ecx
	call __down
	popl %ecx
	popl %edx
1:

down()函数减少*sem信号量的 count 值，然后检查该值是否为负。该值的减少和检查过程必须是原子的。如果count大于等于0，当前进程获得资源并继续正常执行。否则，当前进程必须挂起，将一些寄存器内容压栈后，调用 __down()。这里__down()是下列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

// 挂起当前进程，直到信号量被释放
__attribute__((regparam(3))) void __down(struct semaphore *sem)
{
	DECLARE_WAITQUEUE(wait, current);
	unsigned long flags;
	current->state = TASK_UNINTERRUPTIBLE;
	spin_lock_irqsave(&sem->wait.lock, flags);
	add_wait_queue_exclusive_locked(&sem->wait, &wait);
	sem->sleepers++;
	for(;;)
	{
		if(!atomic_add_negative(sem->sleepers-1, &sem->count))  // count -= 1
		{
			sem->sleepers = 0;   // 如果 count 字段 >= 0，将 sleepers 置 0，表示没有进程在信号量等待队列上睡眠
			break;
		}

	    // 如果 count < 0
		sem->seleepers = 1; 
		spin_unlock_irqrestore(&sem->wait.lock, flags);
		schedule();               // 调用 schedule() 挂起当前进程
		spin_lock_irqsave(&sem->wait.lock, flags);
		current->state = TASK_UNINTERRUPTTIBLE;
	}
	remove_wait_queue_locked(&sem->wait, &wait);
	wake_up_locked(&sem->wait);   // 试图唤醒信号量等待队列中的另一个进程，并终止保持的信号量
	spin_unlock_irqrestore(&sem->wait.lock, flags);
	current->state = TASK_RUNNTING;
}

__down()将当前进程的状态从TASK_RUNNGING变为TASK_UNINTERRUPTIBLE，并把进程放在信号量的等待队列。该函数在访问信号量数据结构的字段前，获得保护信号量等待队列自旋锁sem->wait.lock，并禁止本地中断。当插入和删除元素时，等待队列函数根据需要获取和释放等待队列的自旋锁。__down()的主要任务是挂起当前进程直到信号量被释放。如果没有进程在信号量等待队列上睡眠，则信号量的sleepers字段通常被置为0，否则被置为1。考虑以下几种典型的情况：

• MUTEX信号量打开（count=1，sleepers=0）
  • down宏仅仅把count字段置为0，并跳到主程序的下一条指令；因此，__down()函数根本不执行。
• MUTEX信号量关闭，没有睡眠进程（count=0，sleepers=0）
  • down宏减count并将count字段置为-1 且sleepers字段置为0来调用__down()函数。在循环体的每次循环中，该函数检查count字段是否为负。
    • 如果count字段为负，__down()就调用schedule()挂起当前进程。count字段仍然设置为-1，而sleepers字段置为1,。随后，进程在这个循环内核恢复自己的运行并又进行测试。
    • 如果count字段不为负，则把sleepers置为0，并从循环退出。__down()试图唤醒信号量等待队列中的另一个进程，并终止保持的信号量。在退出时，count字段和sleepers字段都置为0，这表示信号量关闭且没有进程等待信号量。
• MUTEX信号量关闭，有其他睡眠进程（count=-1，sleepers=1）
  • down宏减count并将count字段置为-2且sleepers字段置为1来调用__down()函数。该函数暂时把sleepers置为2，然后通过把sleepers - 1 加到count来取消down宏执行的减操作。同时，该函数检查count是否依然为负。
    • 如果count字段为负，__down()函数把sleepers重新设置为1，并调用schedule()函数挂起当前进程。count字段还是置为-1，而sleepers字段置为1.
    • 如果count字段不为负，__down()函数吧sleepers置为0，试图唤醒信号量等待队列上的另一个进程，并退出持有的信号量。在退出时，count字段置为0且sleepers字段置为0。

down_trylock()函数：适用于异步处理程序。该函数和down()函数除了对资源繁忙情况的处理有所不同之外，其他都是相同的。在资源繁忙时，该函数会立即返回，而不是让进程去睡眠。

down_interruptible()函数：该函数广泛使用在设备驱动程序中，因为如果进程接收了一个信号但在信号量上被阻塞，就允许进程放弃“down”操作。

另外，因为进程通常发现信号量处于打开状态，因此，就可以优化信号量函数。尤其是，如果信号量等待队列为空，up()函数就不执行跳转指令。同样，如果信号量是打开的，down()函数就不执行跳转指令。信号量实现的复杂性是由于极力在执行流的主分支上避免费时的指令而造成的。

读写信号量

类似于读/写自旋锁，不同之处：信号量再次变为打开之前，等待进程挂起而不是自旋转。只有在内核控制路径不持有读信号量和写信号量时，才能获取写信号量。

内核以严格的FIFO顺序处理等待读写信号量的所有进程。如果读者或写者进程发现信号量关闭，这些进程就被插入到信号量等待队列链表的末尾。当信号量被释放时，就检查处于等待队列链表第一个位置的进程。第一个进程常被唤醒。如果是一个写者进程，等待队列上其他的进程就继续睡眠。如果是一个读者进程，那么紧跟第一个进程的其他所有读者进程也被唤醒并获得锁。不过，在写者进程之后排队的读者进程继续睡眠。

数据结构为rw_semaphore：

• count，两个 16 位计数器。高 16 位以二进制补码形式存放非等待写者进程的总数（0 或 1）和等待的写内核控制路径数。低 16 位存放非等待的读者和写者总数。
• wait_list，等待进程的链表。链表中的每个元素是rwsem_waiter结构，包含一个指针和一个标志，指针指向睡眠进程的描述符，标志表示进程为读信号量还是写信号量。
• wait_lock，自旋锁，保护等待队列链表和rw_semaphore结构。

函数：

• init_rwsem()初始化rw_semaphore结构，把count置为0，wait_lock置为未锁，wait_list 置为空链表。
• dwon_read()、down_write()获取读或写信号量。
• up_read()、up_write()释放读或写信号量。
• down_read_trylock()、down_write_trylock()类似于down_read()、down_write()，但在信号量忙的情况下，不阻塞进程。
• downgrade_write()自动将写锁转换为读锁。

补充原语

为了解决多处理器系统上发生的一种微妙的竞争关系，当进程 A 分配了一个临时信号变量，并将其初始化为关闭的 MUTEX，然后将其地址传递给进程 B。A 调用down()，打算一旦被唤醒旧撤销该信号量，而运行在不同 CPU 上的 B 在该信号量上调用up()，结果，up()可能访问一个不存在的数据结构。

上述现象的原因：up()和down()可在同一信号量上并发执行。补充是专门设计来解决以上问题的同步原语。completion包含一个等待队列头和一个标志。

1
2
3
4
5

struct completion 
{
	unsigned int done;   
	wait_queue_head_t wait;
};

与up()对应的叫做complete()，complete()接收completion的地址作为参数，在补充等待队列的自旋锁上调用spin_lock_irqsave()递增 done 字段，唤醒在 wait 等待队列上睡眠的互斥进程，调用spin_unlock_irqrestore()。

与down()对应的叫做wait_for_completion()，接收completion的地址作为参数，并检查done标志，如果 done > 0，说明complete()已在另一个CPU上运行，wait_for_completion()终止。否则wait_for_completion()把current作为一个互斥进程加到等待队列的末尾，将current置为TASK_UNINTERRUPTIBLE状态并让其睡眠。一旦current被唤醒，将其从等待队列中删除。然后函数检查done标志的值，如果done = 0，结束；否则，再次挂起current。

补充原语和信号量之间的真正差别：如何使用等待队列中包含的自旋锁。补充原语中，自旋锁确保complete()和wait_for_completion()不会并发执行。信号量中，自旋锁用于避免并发执行的down()函数弄乱信号量的数据结构。

禁止本地中断

​确保一组内核语句被当做一个临界区处理的主要机制之一就是中断禁止。即使当硬件设备产生了一个IRQ信号时，中断禁止也让内核控制路径继续执行。因此，这就提供了一种有效的方式，确保中断处理程序访问的数据结构也受到保护。然而，禁止本地中断并不保护运行在另一个CPU上的中断处理程序对数据结构的并发访问，因此，在多处理器系统上，禁止本地中断通常与自旋锁结合使用。

宏local_irq_disable()使用cli汇编语言指令关闭本地CPU上的中断，宏local_irq_enable()函数使用sti汇编语言指令打开被关闭的中断。汇编语言指令cli和sti分别清除和设置eflags控制寄存器的IF标志。如果eflags寄存器的IF标志被清零，宏irqs_disabled()产生等于1的值；如果IF标志被设置，该宏也产生为1的值。

中断可以以嵌套方式执行，因此内核在临界区末尾不能简单设置 IF 标志。控制路径必须保存先前赋给 IF 标志的置，并在执行结束时恢复它。

保存和恢复eflags的内容是分别通过宏local_irq_save()和local_irq_restore()宏来实现的。local_irq_save宏把eflags寄存器的内容拷贝到一个局部变量中，随后用cli汇编语言指令把IF标志清零。在临界区的末尾，宏local_irq_restore恢复eflags原来的内容。因此，只有在这个控制路径发出cli汇编指令之前，中断被激活的情况下，中断才处于打开状态。

禁止和激活可延迟函数

禁止可延迟函数在一个 CPU 上执行的一种简单方式是禁止在那个 CPU 上的中断，使得软中断不能异步开始。另一种方式是禁止可延迟函数而不禁止中断，通过操作当前thread_info描述符preempt_count字段中存放的软中断计数器即可。

如果软中断计数器是正数，do_softirq() 函数就不会执行。tasklet 会在软中断之前被执行，并将该计数器设置为大于 0 的值。

宏local_bh_disable给本地 CPU 的软中断计数器加 1。local_bh_enable()函数从本地 CPU 的软中断计数器中减 1。内核因此能使用几个嵌套的local_bh_disable调用，只有宏local_bj_enable与第一个local_bh_disable调用相匹配，可延迟函数才再次被激活。

递减软中断计数器后，local_bh_enable执行两个重要操作以有助于保证适时执行长时间等待的进程：

• 如果本地 CPU 的preempt_count字段中硬中断计数器和软中断计数器的值都等于 0，且有挂起的软终端，就调用do_softirq()激活这些软中断。
• 如果本地 CPU 的TIF_NEED_RESCHED标志被设置，说明进程切换请求时挂起的，调用preempt_schedule()。

对内核数据结构的同步访问

系统性能可能随所选择的同步原语种类的不同而有很大变化。通常情况下，内核开发者采用下述由经验得到的法则：把系统中的并发度保持在尽可能高的程度。系统中的并发度取决于两个主要因素：

• 同时运转的I/O设备数；
• 进行有效工作的CPU数。

为了使I/O吞吐量最大化，应该使中断禁止保持在很短的时间。当中断被禁止时，由I/O设备产生的IRQ被PIC暂时忽略，因此，就没有新的活动在这种设备上开始。

为了有效地利用CPU，应该尽可能避免使用基于自旋锁的同步原语。当一个CPU执行紧指令循环等待自旋锁打开时，是在浪费宝贵的机器周期。同时，由于自旋锁对硬件高速缓存的影响而使其对系统的整体性能产生不利影响。

在自旋锁、信号量及中断禁止之间选择

只要内核控制路径获得自旋锁（还有读/写锁、顺序锁或 RCU“读锁”），就禁用本地中断或本地软中断，自动禁用内核抢占。

保护异常所访问的数据结构

当一个数据结构仅由异常处理程序访问时，最常见的产生同步问题的异常就是系统调用服务例程，在这种情况下，CPU运行在内核态而为用户态程序提供服务。因此，仅由异常访问的数据结构通常表示一种资源，可以分配给一个或多个进程。竞争条件可以通过信号量避免，因为信号量原语允许进程陲眠到资源变为可用。

保护中断所访问的数据结构

中断处理程序本身不能同时多次运行。因此，访问数据结构就无需任何同步原语。但是，如果多个中断处理程序访问一个数据结构，情况就有所不同了。一个处理程序可以中断另一个处理程序，不同的中断处理程序可以在多处理器系统上同时运行。没有同步，共享的数据结构就很容易被破坏。

单处理器系统中，必须在中断处理程序的所有临界区上禁止中断来避免竞争条件，其他同步原语都不行。因为信号量能阻塞进程，自旋锁可能使系统冻结。多处理器系统中，避免竞争条件最简单的方法是禁止本地中断，并获取保护数据结构的自旋锁或读/写自旋锁。

Linux内核使用了几个宏，把本地终端激活/禁止与自旋锁结合。

保护被可延迟函数所访问的数据结构

单处理器系统上不存在竞争条件，因为可延迟函数的执行总是在一个 CPU 上串行执行，不需要同步原语。多处理器系统上存在竞争条件，因为几个可延迟函数可以并发执行。

由软中断访问的数据结构必须受到保护，通常使用自旋锁，因为同一个软中断可在多个 CPU 上并发运行。仅由一种 tasklet 访问的数据结构不需要保护，因为同种 tasklet 不能并发执行。由几种 tasklet 访问，必须对数据结构进行保护。

保护由异常和中断访问的数据结构

单处理系统上，因为中断处理程序是不是可重入的且不能被异常中断，只要内核以本地中断禁止访问数据结构，内核在访问数据结构的过程中就不会被中断。如果数据结构被一种中断处理程序访问，中断处理程序不用禁止本地中断就可访问数据结构。多处理器系统上，必须关注异常和中断在其他CPU上的并发执行。本地中断禁止必须外加自旋锁，强制并发的内核控制路径等待，直到访问数据结构的处理程序完成自己的工作。

有时使用信号量代替自旋锁可能更好。因为中断处理程序不能被挂起，必须用紧循环和down_trylock()函数获得信号量，在这里，信号量的作用与自旋锁一样。系统调用服务例程可在信号量忙时挂起调用进程，提高系统并发度。

保护由异常和可延迟函数访问的数据结构

保护由异常和可延迟函数访问的数据结构与异常和中断处理程序访问的数据结构处理方式类似。可延迟函数本质上是由中断的出现激活的，而可延迟函数执行时不可能产生异常。因此，把本地中断禁止与自旋锁结合起来即可。

异常处理程序可通过使用local_bh_disable()宏禁止可延迟函数，而不禁止本地中断。在每 CPU 上可延迟函数的执行都被串行化，不存在竞争条件。多处理器系统上，使用自旋锁可确保任何时候只有一个内核控制路径访问数据结构。

保护由中断和可延迟函数访问的数据结构

类似于中断和异常访问的数据结构。可延迟函数执行期间禁用本地中断。没有其他的中断处理程序访问数据结构时，中断处理程序可随意访问被可延迟函数访问的数据结构而不用关中断。多处理器系统上，需要自旋锁禁止对多个 CPU 上数据结构的并发访问。

保护由异常、中断和可延迟函数访问的数据结构

禁止本地中断和获取自旋锁几乎总是避免竞争条件所必须的，但没有必要显式禁止可延迟函数。

避免竞争条件的实例

引用计数器

引用计数器广泛应用于内核中以避免由于资源的并发分配和释放而产生的竞争条件。它是一个atomic_t计数器，与特定的资源，如内存页、模块或文件相关。当内核控制路径开始使用资源，原子地减少计数器值；当内核控制路径用完资源，原子地增加计数器值。原子计数器变为 0，说明资源未被使用，如果必要，释放该资源。

大内核锁

大内核锁是相对粗粒度的自旋锁，确保每次只有一个进程运行在内核态。在2.2和2.4版本中具有极大的灵活性，不再依赖一个单独的自旋锁，而是由许多不同的自旋锁保护大量的内核数据结构。从2.6.11开始，用叫kernel_sem的信号量实现大内核锁，但比信号量复杂。每个进程描述符含有lock_depth字段，允许同一个进程几次获得大内核锁。对大内核锁两个连续的请求不挂起处理器。字段为-1表示，进程未获得过锁；字段为正数，表示请求了多少次锁。lock_depth对中断处理程序、异常处理程序以及可延迟函数获取大内核锁都是至关重要的，如果没有这个字段，那么在当前进程已经有大内核锁的情况下，任何试图获得这个锁的异步函数都可能产生死锁。

lock_kernel()获得大内核锁：

1
2
3
4

depth = current->lock_depth + 1;
if(depth == 0)
	down(&kernel_sem);
current->lock_depth = depth;

unlock_kernel()释放大内核锁：

1
2

if(--current->lock_depth < 0)
	up(&kernel_sem);

持有大内核锁的进程可调用schedule()放弃 CPU。不过schedule()检查被替换进程的lock_depth字段，如果它的值是正数或0，则自动释放kernel_sem信号量。因此不会有显式调用schedule()的进程在进程切换前后都保持大内核锁。

当一个持有大内核锁的进程被强占时，schedule()一定不能释放信号量，因为在临界区内执行代码的进程没有主动触发进程切换。

为避免被强占的进程事情大内核锁，preempt_schedule_irq()临时把进程的lock_depth字段设置为 -1，这样schedule()假定被替换的进程不拥有 kernel_sem信号量，也就不能释放它。一旦该进程再次被调度程序选中，preempt_schedule_irq()函数就恢复lock_depth原来的值，并让进程在被大内核锁保护的临界区中继续执行。

内存描述符读/写信号量

mm_struct类型的每个内存描述符在mmap_sem字段中都包含了信号量。因为几个轻量级进程之间可以共享一个内存描述符，因此信号量可保护该描述符，以避免可能产生的竞争条件。这种信号量为以读/写信号量方式实现，因为一些内核函数，如缺页异常处理程序只需要扫描内存描述符。

slab 高速缓存链表的信号量

slab 高速缓存描述符链表是通过cache_chain_sem信号量保护的，允许互斥地访问和修改该链表。当kmem_cache_create()在链表中增加一个新元素，而kmem_cache_shrink()和kmem_cache_reap()顺序地扫描整个链表时，可能产生竞争条件。

索引节点的信号量

Linux 把磁盘文件的信息存放在一种叫做索引节点的内存对象中。相应的数据结构包括自己的信号量，存放在i_sem字段中。在文件系统的处理过程中会出现很多竞争条件。竞争条件都可以通过用索引节点信号量保护目录文件来避免。只要一个程序使用了两个或多个信号量，就存在死锁的可能，因为两个不同的控制路径可能互相死等着释放信号量。在有些情况下，内核必须获得两个或更多的信号量锁。索引节点信号量倾向于这种情况，例如，在rename()系统调用的服务例程中就会发生这种情况。在这种情况下，操作涉及两个不同的索引节点，因此，必须采用两个信号量。为了避免这样的死锁，信号量的请求按预先确定的地址顺序进行。

定时测量

很多计算机化的活动都是由定时测量（timing measurement）来驱动的，这常常对用户是不可见的。Linux内核必需完成两种主要的定时测量，我们可以对此加以区别：

• 保存当前时间和日期，以便能通过time()，ftime()，gettimeofday()系统调用把它们返回给用户程序，也可以由内核本身把当前时间作为文件和网络包的时间戳。
• 维持定时器，这个机制能够告诉内核或用户程序某一时间间隔已经过去了。

定时测量是由基于固定频率振荡器和计数器的几个硬件电路完成的。

时钟和定时器电路

在80x86体系结构上，内核必须显式地与集中时钟和定时器电路打交道。时钟电路同时用于跟踪当前时间和产生精确的事件量度。

实时时钟（RTC）

所有PC都包含一个叫实时时钟（real Time Clock RTC）的时钟，它独立于CPU和所有其他芯片的。即使当PC被切断电源，RTC还继续工作，因为它靠一个小电池或蓄电池供电。RTC能在IRQ8上周期性的发出中断，频率在2~8192Hz之间。也可以对RTC进行编程以使当RTC到达某个特定的值是激活IRQ8线，也就是作为一个闹钟来工作。Linux只用RTC来获取事件和日期，不过，通过对/dev/rtc设备文件进行操作，也允许进程对RTC编程。

时间戳计数器（TSC）

所有的80x86微处理器都包含一条CLK输入引线，它接受外部振荡器的时钟信号。计数器在每个时钟信号到来时加1，该计数器利用时间戳计数器TSC寄存器来实现，通过指令rdtsc访问。Linux利用这个寄存器能获得更精确的时间测量，为了做到这点Linux必须在初始化时确定时钟信号的频率。算出CPU实际频率的任务是在系统初始化期间完成的。calibrate_tsc()通过计算一个大约在5ms的时间间隔内所产生的时钟信号的个数来计算CPU的实际频率。

可编程间隔定时器（PIT）

PIT的作用类似于微波炉的闹钟，即让用户意识到烹调的时间间隔已经过去了。所不同的是，这个设备不是通过振铃，而是发出一个特殊的中断，叫做时钟中断来通知内核又一个时间间隔过去了。

时钟中断的频率取决于体系结构，较慢的机器其节拍大概为10ms，而较快的机器的节拍大概1ms。在Linux中有几个宏产生决定时钟中断频率的常量：

• HZ产生每秒时钟中断的近似个数，也就是时钟中断的频率。
• CLOCK_TICK_RATE产生的值为1193182，这个是是振荡器频率。
• LATCH产生CLOCK_TICK_RATE和HZ的比值再四舍五入后的整数值。这个值用来对PIT编程。

PIT由setup_pit_timer()进行初始化

outb()等价于outb汇编指令，把第一个操作数拷贝到第二个操作数指定的IO端口。outb_p()类似于outb()，不过，它会通过一个空操作而产生一个暂停，以避免使硬件难以分辨。udelay()宏函数引入一个更短的延迟。第一条outb_p()让PIT以新的频率产生中断。接下来的两条outb_p()和outb()为设备提供新的中断频率。把16位LATCH常量作为两个连续的字节发送到设备的8位IO端口0x40，结果，PIT将以1000Hz的频率产生时钟中断。

CPU本地定时器

CPU本地定时器是一种能够产生单步中断或周期性中断的设备，它类似于可编程间隔定时器APIC，区别：

• APIC计数器是32位，而PIC计数器是16位； 因此，可以对本地定时器编程来产生很低频率的中断
• 本地APIC定时器把中断只发送给自己的处理器，而PIT产生一个全局性中断，系统中的任一CPU都可以对其处理。
• APIC定时器是基于总线时钟信号的。每隔1,2,4,8,16,32,64或128总线时钟信号到来时对该定时器进行递减可以实现对其编程的目的。相反，PIT有其自己的内部时钟振荡器，可以更灵活地编程。

高精度事件定时器(HPET)

高精度事件定时器是由Intel和Microsoft联合开发的一种新型定时器芯片。尽管这种定时器在终端用户机器上还并不普遍，但Linux2.6已经能够支持它们。

ACPI电源管理定时器

ACPI电源管理定时器（或称ACPI PMT）是另一种时钟设备，包含在几乎所有基于ACPI的主板上。它的时钟信号拥有大约为3.58MHz的固定频率。该设备实际上是一个简单的计数器， 它在每个时钟节拍到来时增加一次。为了读取计数器的当前值，内核需要访问某个I/O端口，该I/O端口的地址由BIOS在初始化阶段确定。

如果操作系统或者BIOS可以通过动态降低CPU的工作频率或者工作电压来节省电池的电能，那么ACPI电源管理定时器就比TSC更优越。当发生ACPI PMT的频率不会改变。而另一方面，TSC计数器的高频率非常便于测量特别小的时间间隔。

Linux计时体系结构

Linux必定执行与定时相关的操作。例如，内核周期性地：

• 更新自系统启动以来所经过的时间
• 更新时间和日期
• 确定当前进程在每个CPU上已运行了多长时间，如果已经超过了分配给它的时间，则抢占它。时间片（也叫时限）
• 更新资源使用统计数
• 检查每个软定时器的时间间隔是否已到。

Linux的计时体系结构(time keeping architecture)是一组与时间流相关的内核数据结构和函数，

• 在单处理器系统上，所有的计时活动都是由全局定时器（可以是可编程间隔定时器也可以是高精度事件定时器）产生的中断触发的
• 在多处理器系统上，所有普通的活动（像软定时器的处理）都是由全局定时器产生的中断触发的，而具体CPU的活动是由本地APIC定时器产生的中断触发的。

计时体系机构的数据结构

定时器对象

为了使用一种统一的方法来处理可能存在的定时器资源，内核使用了定时器对象，它是timer_opts类型的一个描述符，该类型由定时器名称和四个标准的方法组成，如表6-1所示：

定时器对象中最重要的方法是mark_offset和get_offset。mark_offset方法由时间中断处理程序调用，并以适当的数据结构记录每个节拍到来时的准确时间。get_offset方法使用已记录的值来计算自上一次时钟中断(节拍)以来经过的时间(us为单位)。由于这两种方法，使得Linux计时体系结构能够达到子节拍的分辨度，也就是说，内核能够以比节拍周期更高的精度来测定当前的时间，这种操作被称作定时插补(timerinterpolation)。

变量cur_timer存放了某个定时器对象的地址，该定时器是系统可利用的定时器资源中“最好的”，内核初始化期间，select_timer()设置cur_timer指向适当定时器对象的地址。表6-2以优先级顺序列出了80x86体系结构中最常用的定时器对象。定时插补一列列出了定时器对象的mark_offset和get_offset使用的定时器源，

jiffies变量

jiffies变量是一个计数器，用来记录自系统启动以来产生的节拍总数。每次时钟中断发生时（每个节拍）它便加1.在80x86体系结构中，jiffies是一个32位的变量，因此每隔大约50天它的值会回绕(wraparound)到0，这对Linux服务器来说是一个相对较短的时间间隔。不过，由于使用了time_after、time_afer_eq、time_before和time_before_eq四个宏，内核干净利索地处理了jiffies变量的益出。

jiffies被初始化为0xfffb6c20，它是一个32位有符号值，正好等于-300000。因此计数器将会在系统启动5分钟内处于溢出状态，使得那些不对jiffies做溢出检查的有缺陷代码在开发阶段被及时发现。

但是内核需要自系统启动以来产生的系统节拍的真实数目。在80x86系统中，jiffies变量通过连接器被换算成一个64位计数器的低32位，这个64位的计数器被称作jiffies_64。在1ms为一个节拍的情况下，jiffies_64变量将会在数十亿年后才发生回绕，所以我们可以放心地假定它不会溢出。

在32位系统中不能自动对64位变量进行访问，因此需要一些同步机制当两个32位计数器（由这两个32位计数器组织为64位计数器）的值在被读取时这个64位的计数器不会被更新，结果是每个64位的读操作明显比32位的读操作更慢。

get_jiffies_64()用来读取jiffies_64的值并返回该值。

xtime_lock()顺序锁用来保护64位的读操作：该函数一直读jiffies_64直到确认该变量并没有同时被其他内核控制路径更新才读取jiffies_64。当在临界区增加jiffies_64的值时必须用write_seqlock(&xtime_lock)和write_sequnlock(&xtime_lock)进行保护。

xtime变量

xtime变量存放当前时间和日期；它是一个timespec类型的数据结构，该结构有两个字段：

• tv_sec：存放自1970年1月1日(UTC)午夜以来经过的秒数
• tv_nsec:存放自上一秒开始经过的纳秒数

xtime变量通常是每个节拍更新一次，也就是说，大约每秒更新1000次。用户程序从xtime变量获得当前时间和日期。内核也经常引用它。xtime顺序锁消除了对xtime的同时访问而可能发生的竞争条件。

单处理器系统上的计时体系结构

在单处理器系统上，所有与定时有关的活动都是由IRQ线0上的可编程间隔定时器产生的中断触发的。

初始化阶段

在内核初始化期间，time_init()函数被用来建立计时体系结构，它通常执行如下操作：

1. 初始化xtime变量。利用get_cmos_time()函数从实时时钟上读取自1970年1月1日(UTC)午夜以来经过的秒数。设置xtime的tv_nsec字段，使得即将发生的jiffies变量溢出与tv_sec字段保持一致，也就说，它将落到秒的范围内。
2. 初始化wall_to_monotonic变量，它存放将被加到xtime上的秒数和纳秒数。
3. 如果内核支持HPET，它将调用hpet_enable()函数来确认ACPI固件是否探测到了该芯片并将它的寄存器映射到了内存地址空间中。
4. 调用select_timer()来挑选系统中可利用的最好的定时器资源，并设置cur_timer变量指向该定时器资源对应的定时器对象的地址。
5. 调用setup_irq(0, &irq0)来创建与IRQ0相应的中断门，IRQ0引脚线连接着系统时钟中断源(PIT或HPET)。irq0变量被静态定义如下：struct irqaction irq0 = {timer_interrupt, SA_INTERRUPT, 0, "timer", NULL, NULL);。从现在起，timer_interrupt()函数将会在每个节拍到来时被调用，而中断被禁止，因为IRQ0主描述符的状态字段中的SA_INTERRUPT标志被置位。

时钟中断处理程序

timer_interrupt()函数是PIT或HPET的中断服务例程，它执行以下步骤：

• 在xtime_lock顺序锁上产生一个write_seqlock()来保护与定时相关的内核变量。
• 执行cur_timer定时器对象的mark_offset方法。正如前面的”计时体系结构的数据结构”一节解释的那样，有四种可能的情况：
  • cur_timer指向timer_hpet对象；这种情况下，HPET芯片作为时钟中断源。mark_offset方法检查自上一个节拍以来是否丢失时钟中断，在这种不太可能发生的情况下，它会相应地更新jiffies_64。接着，该方法记录下HPET周期计数器的当前值。
  • cur_time指向timer_pmtmr对象；在这种情况下PIT芯片作为时钟中断源，但是内核使用APIC电源管理定时器以更高的分辨度来测量时间。mark_offset方法检查自上一个节拍以来是否丢失时钟中断，如果丢失则更新jiffies_64。然后，它记录APIC电源管理定时器计数器的当前值。
  • cur_time指向timer_tsc对象；在这种情况下，PIT芯片作为时钟中断源，但是内核使用时间戳计数器以更高的分辨度来测量时间。mark_offset方法执行与上一种情况相同的操作。
  • cur_timer指向timer_pit对象；这种情况下，PIT芯片作为时钟中断源，除此之外没有别的定时器电路。mark_offset方法什么也不做。
• 调用do_timer_interrupt()函数，do_timer_interupt()函数执行以下操作：
  • 使jiffies_64的值增加1。注意，这样做是安全的，因为内核控制路径仍然为写操作保持着xtime_lock顺序锁。
  • 调用update_times()函数来更新系统日期和时间，并计算当前系统负载。
  • 调用update_process_times()函数为本地CPU执行几个与定时相关的计数操作。
  • 调用profile_tick()函数。
  • 如果使用外部时钟来同步系统时钟，则每隔660秒调用一次set_rtc_mmss()函数来调整实时时钟。这个特性用来帮助网络中的系统同步它们的时钟。
• 调用write_sequnlock()释放xtime_lock顺序锁。
• 返回值1，报告中断已经被有效地处理了。

多处理器系统上的计时体系结构

多处理器系统可以依赖两种不同的时钟中断源：可编程间隔定时器或高精度事件定时器产生的中断，以及CPU本地定时器产生的中断。在linux2.6中，PIT或HPET产生的全局时钟中断触发不涉及具体CPU的活动，比如处理器软定时器和保持系统时间的更新。相反，一个CPU本地时间中断触发涉及本地CPU的计时活动，例如监视当前进程的运行时间和更新资源使用统计数。

初始化阶段

全局时钟中断处理程序由time_imit()函数初始化。Linux内核为本地时钟中断保留第239号中断向量。初始化阶段，函数apic_intr_init()根据239号向量和低级中断处理程序apic_timer_interrupt()的地址设置IDT的中断门。函数calibrate_APIC_clock()通过正在启动的CPU的本地APIC来计算在一个节拍内收到了多少个总线时钟信号。这个确切的值被用来对本地所有APIC编程，并由此在每个节拍产生一次本地时钟中断。这是由setup_APIC_timer()完成，该函数被系统中的每个CPU执行一次。

全局时钟中断处理程序

SMP版本的timer_interrupt()处理程序与UP版本的该处理程序在几个地方有差异：

• timer_interrupt()调用函数do_timer_interrupt()向IO APIC芯片的一个端口写入，以应答定时器的中断。
• update_process_times()函数不被调用，因为该函数执行与特定CPU相关的操作
• profile_tick()不被调用，因为该函数同样执行与特定CPU相关的操作。

本地时钟中断处理程序

处理程序执行系统中与特定CPU相关的计时活动，即监管内核代码并检测当前进程在特定CPU上已经运行了多长时间。apic_timer_interrupt()等价于：

该低级处理函数与其他低级中断处理函数相似，被称作smp_apic_timer_interrupt()的高级中断处理函数执行如下步骤：

• 获得CPU逻辑号
• 使irq_stat数组中第n项的apic_timer_irqs字段加一
• 应答本地APIC上的中断
• 调用irq_enter()函数
• 调用smp_local_timer_interrupt()函数
• 调用irq_exit()函数

smp_local_timer_interrupt()函数执行每个CPU的计时活动，执行下边的主要步骤。

• 调用profile_tick()函数
• 调用update_process_times()函数检查当前进程运行的时间并更新一些本地CPU统计数

更新时间和日期

用户程序从xtime变量中获得当前时间和日期。内核必须周期性地更新该变量，才能使它的值保持相当的精确。全局时钟中断处理程序调用update_times()函数更新xtime变量的值。

全局时钟中断处理程序调用update_time()函数更新xtime()的值：

1
2
3
4
5
6
7
8
9

void update_times(void) {
	unsigned long ticks;
	ticks = jiffies - wall_jiffies;
	if(ticks) {
		wall_jiffies += ticks;
		update_wall_time(ticks);
	}
	calc_load(ticks);
}

wall_jiffies变量存放xtime变量最后更新的时间。内核不必每个时钟节拍更新xtime变量。然而最后不会有时钟节拍丢失。因此，xtime最终存放正确的系统时间。update_wall_time()函数连续调用update_wall_time_one_tick()函数ticks次，每次调用都给xtime.tv_nsec字段加上1000000。如果xtime.tv_nsec大于999999999，那么update_wall_time()函数还会更新xtime的tv_sec字段。如果系统发出adjtimex()系统调用，那么函数可能会稍微调整1000000这个值使时钟稍快或稍慢一点。

更新系统统计数

内核在与定时相关的其他任务中必须周期性地收集若干数据用于：

• 检查运行进程的CPU资源限制
• 更新与本地CPU工作负载有关的统计数
• 计算平均系统负载
• 监管内核代码

更新本地CPU统计数

单处理器系统上的全局时钟中断处理程序或多处理器系统上的本地时钟中断处理程序调用update_process_times()函数来更新一些内核统计数。该函数执行以下步骤：

• 检查当前进程运行了多长时间。当时钟中断发生时，根据当前进程运行在用户态还是内核态，选择调用account_user_time()还是account_system_time()。每个函数基本上执行如下步骤。
  • 更新当前进程描述符的utime字段或stime字段。在进程描述符中提供两个被称作cutime和cstime的附加字段，分别用来统计子进程在用户态和内核态下所经过的CPU节拍数。由于效率的原因，update_process_times()并不更新这些字段，而只是当父进程询问它的其中一个子进程的状态时才对其进行更新。
  • 检查是否已达到总的CPU时限，如果是，向current进程发送SIGXCPU和SIGKILL信号
  • 调用account_it_virt()和account_it_prof()来检查进程定时器。
  • 更新一些内核统计数，这些统计数存放在每CPU变量kstat中。
• 调用raise_softirq()来激活本地CPU上的TIMER_SOFTIRQ任务队列。
• 如果必须回收一些老版本的，受RCU保护的数据结构，那么检查本地CPU是否经历了静止状态并调用tasklet_schedule()来激活本地CPU的rcu_tasklet任务队列。
• 调用scheduler_tick()函数，该函数使当前进程的时间片计数器减1，并检查计数器是否已减到0

记录系统负载

用户输入uptime命令后可以看到一些统计数据：如相对于最后1分钟，5分钟，15分钟的”平均负载”。在单处理器系统上，值0意味着没有活跃的进程在运行，而值1意味着一个单独的进程100％占有CPU，值大于1说明几个运行着的进程共享CPU。

update_times()在每个节拍都要调用calc_load()函数来计算处于TASK_RUNNING或TASK_UNINTERRUPTIBLE状态的进程数，并用这个数据更新平均系统负载。

监管内核代码

Linux包含一个被称作readprofiler的最低要求的代码监管器，检测在内核态的什么地方花费时间。监管器确定内核的热点——执行最频繁的内核代码片段。它基于非常简单的蒙特卡洛算法；在每次时钟中断发生时，内核确定该中断是否发生在内核态；如果是，内核从堆栈取回中断发生前的eip寄存器的值。并用这个值揭示中断发生前内核正在做什么。最后，采样数据积聚在“热点”上。

profile_tick()函数为代码监管器采集数据。这个函数在单处理器系统上是由do_timer_interrup()调用的，在多处理器系统上是由smp_local_timer_interrup()函数调用的。

为了激活代码监管器，在Linux内核启动时必须传递字符串参数profile=N，这里2的N的次方表示要监管的代码段的大小，采集的数据可以从/proc/profile文件中读取。可以通过修改这个文件来重置计数器；在多处理器系统上，修改这个文件还可以改变抽样频率。不过，内核开发者并不直接访问/proc/profile文件，而是用readprofile系统命令。

Linux2.6内核还包含了另一个监管器，叫做oprofile，oprofile除了更灵活，更可定制外，还能用于发现内核代码，用户态应用程序及系统库中的热点。当使用ofrofile时，profile_tick()调用timer_notify()函数来收集这个新监管器所使用的数据。

检查非屏蔽中断监视器

Linux提供了看门狗系统，这对于探测引起系统冻结的内核bug可能相当有用。为了激活这样的看门狗，必须在内核启动时传递nmi_watchdog参数。

看门狗基于本地和I/O APIC一个巧妙的硬件特性；它们能在每个CPU上产生周期性的NMI中断，因为NMI中断是不能用汇编语言指令cli屏蔽的，所以，即使禁止中断，看门狗也能检测到死锁。

因而，一旦每个时钟节拍到来，所有的CPU，不管其正在做什么，都开始执行NMI中断处理程序；该中断处理程序又调用do_nmi()。这个函数获得CPU的逻辑号n，然后检查irq_stat数组第n项的apic_timer_irqs字段。如果该CPU字段工作正常，那么，第n项的值必定不同于在前一个NMI中断中读出的值。当CPU正常运行时，第n项的apic_timer_irq字段就会被本地时钟中断处理程序增加，如果计数器没有增加，说明本地时钟中断处理程序在整个时钟节拍期间根本就没有被执行。

当NMI中断处理程序检测到一个CPU冻结时，就会敲响所有的钟：它把引起恐慌的信息记录在系统日志文件中，转储该CPU寄存器的内容和内核栈的内容。最后杀死当前进程，这就为内核开发者提供了发现错误的机会。

软定时器和延迟函数

定时器允许在将来的某个时刻，函数在给定的时间间隔用完时被调用。超时（time-out）表示与定时器相关的时间间隔已经用完的那个时刻。

每个定时器都包含一个字段，表示定时器将需要多长时间才能到期。这个字段的初值就是jiffies的当前值加上合适的节拍数。这个字段的值不再改变，当jiffies大于或等于这个字段存放的值时，定时器到期。

Linux考虑两种类型的定时器， 即动态定时器 (dynamic timer)和间隔定时器 (internal timer).第一种类型由内核使用，而间隔定时器可以由进程的用户态创建。

因为对定时器函数的检查总是由可延迟函数进行，而可延迟函数被激活以后很长时间才能被执行，因此，内核不能确保定时器函数正好在定时期间开始执行，而只能保证在适当的时间执行它们，或者假定延迟到几百毫秒之后执行它们。

动态定时器

动态定时器被动态的创建和撤销，对当前活动的动态定时器的个数没有限制。动态定时器存放在下列timer_list结构中：

1
2
3
4
5
6
7
8
9

struct timer_list{
	struct list_head entry;
	unsigned long expires;
	spinlock_t lock;
	unsigned long magic;
	void (*function)(unsigned long);
	unsigned long data;
	tvec_base_t *base;
};

为了创建并激活一个动态定时器，内核必须：

• 如果需要，创建一个新的timer_list对象，比如说设为t。这可以通过以下几种方式来进行：
  • 在代码中定义一个静态全局变量
  • 在函数内定义一个局部变量；在这情况下，这个对象存放在内核堆栈中。
  • 在动态分配的描述符中包含这个对象。
• 调用init_timer(&t)函数初始化这个对象。实际上是把t.base指针字段置为NULL并把t.lock自旋锁设为”打开”.
• 把定时器到期时激活函数的地址存入funciton字段。如果需要，把传递给函数的参数值存入data字段。
• 如果动态定时器还没有被插入到链表中，给expires字赋一个合适的值并调用add_timer(&t)函数把t元素插入到合适的链表中。
• 否则，如果动态定时器已经插入到链表中，则调用mod_timer()函数来更新expires字段，这样也能将对象插入到合适的链表中。

一旦定时器到期，内核就自动把元素t从它的链表中删除。不过，有时进程应该用del_timer()、del_timer_sync()或del_singleshot_timer_syn()函数显式地从定时器链表中删除一个定时器。事实上，在定时器到时期之前，睡眠的进程可能被唤醒，在这种情况下，唤醒的进程就可以选定撤消某个定时器。虽然从链表中已删除的定时器上调用del_timer()没什么害处。不过，在定时器函数内删除定时器是一种的习惯做法。

在linux2.6中，动态定时器需要CPU来激活，也就是说，定时器函数总会在每一个执行add_timer()或稍后执行mod_timer()函数的那同一个CPU上运行。不过，del_timer()及与其类似的函数能使所有动态定时器无效，即使该定时器并不依赖于本地CPU激活。

动态定时器与竞争条件

被异步激活的的动态定时器有参与竞争条件的倾向。例如，考虑一个动态定时器，它的函数作用于可丢弃的资源。如果在定时器函数被激活时资源不存在，那么不停止定时器就释放资源势必导致数据结构的崩溃。因此，一种凭经验的做法就是在释放资源前停止定时器:

1
2

del_timer(&t);
X_release_Resources();

然后，在多处理器系统上，这段代码是不安全的，因为当调用del_timer()函数时，定时器函数可能已经在其它CPU上运行了。结果，当定时器函数还作用在资源上时，资源可能被释放。为了避免这种竞争条件，内核提供了del_timer_sync()函数。这个函数从链表中删除定时器，然后检查定时器函数是否还在其它CPU上运行；如果是，del_timer_sync()就等待，直到定时器函数结束。

del_timer_sync()函数相当复杂，而且执行速度慢，因为它必须小心考虑这种情况：定时函数重新激活它自己。如果内核开发者知道定时器从不重新激活定时器，她就能使用更简单更快速的del_singleshot_timer_sync()函数来使定时器无效，并等直到定时器函数结束。

当然，也存在其它种类的竞争条件。例如，修改已激活定时器expires字段的正确方法是调用mod_timer()，而不是删除定时器随后又创建它。在后一种方法中，要修改同一定时器expires字段的两个内核控制路径可能糟糕地交错在一起。定时器函数在SMP上的安全实现是通过每个timer_list对象包含的lock自旋锁达到的：每当内核必须访问动态定时器的链表时，就禁止中断并猎取这个自旋锁。

动态定时器的数据结构

基于一种巧妙的数据结构，即把expires值划分成不同的大小，并允许动态定时器从大expires值的链表效率到小expires值的链表进行有效的过滤。此外，在多处理器系统中活动的动态定时器集合被分配到各个不同的CPU中。

动态定时器的主要数据结构是一个叫做tvec_bases的每CPU变量；它包括NR_CPUS个元素，系统中每个CPU各有一个。每个元素是一个tvec_base_t类型的数据结构，它包含相应CPU中处理动态定时器需要的所有数据。

1
2
3
4
5
6
7
8
9
10

typedef struct tvec_t_base_s{
	spinlock_t lock;
	unsigned long timer_jiffies;
	struct timer_list *running_timer;
	tvec_root_t tvl
	tvec_t tv2;
	tvec_t tv3;
	tvec_t tv4;
	tvec_t tv5;
} tver_base_t;

字段tv2、tv3和tv4的数据结构都是tvec_t类型，该类型有一个数组vec。这些链表包含在紧接着到来的2的14次减1等几个节拍内将要到期的所有动态定时器。

字段tv5与前面的字段几乎相同，但唯一区别就是vec数组的最后一项是一个大expires字段值的动态定时器链表。tv5从不需要从其它的数组补充。图6-1用图例说明了5个链表组。

timer_jiffies字段的值表示需要检查的动态定时器的最早到期时间；如果这个值与jiffies的值一样，说明可延迟函数没有积压；如果这个值小于jiffies，说明前几个节拍相关的可延迟函数必须处理。该字段在系统启动时被设置成jiffies的值，且只能由run_timer_softirq()函数增加它的值。注意当处理动态定时器的可延迟函数在很长一段时间内都没有被执行时，timer_jiffies字段的值表示需要检查的动态定时器的最早到期时间；如果这个值与jiffies的值一样，说明可延迟函数没有积压；如果这个值小于jiffies,说明前几个节拍相关的可延迟函数必须处理。该字段在系统启动时被设置成jiffies的值，且只能由run_timer_softirq()函数增加它的值。注意当处理动态定时器的可延迟函数在很长一段时间内都没有被执行时，timer_jiffies字段可能会落后jiffies许多。

在多处理器系统中，字段running_timer指向由本地CPU当前正处理的动态定时器timer_list数据结构。

动态定时器处理

尽管软定时器具有巧妙的数据结构，但是对其处理是一种耗时的活动，所以不应该被时钟中断处理程序执行。在Linux2.6中该活动由延迟函数来执行，也就是由TIMER_SOFTIRQ软中断行。

run_timer_softirq()函数是与TIMER_SOFTIRQ软中断请求相关的可延迟函数。它实质上执行如下操作：

• 把与本地CPU相关的tvec_base_t数据结构的地址存放到base本地变量中。
• 获得base->lock自旋锁并禁止本地中断
• 开始执行一个while循环，当base->timer_jiffies大于jiffies的值时终止，在每一次循环过程中，执行下列子步骤：
  • 计算base->tv1中链表的索引，该索引保存着下一次将要处理的定时器：index =base->timer_jiffies &255
  • 如果索引值为0，说明base->tv1中的所有链表已经被检查过了，所以为空；于是该函数通过调用cascade()来过滤动态定时器
    • if(!index && (!cascade(base, &base->tv2, (base->timer_jiffies>>8)&63)) && (!cascade(base, &base->tv3, (base->timer_jiffies>>14)&63)) && (!cascade(base, &base->tv4, (base->timer_jiffies>>20)&63)) && (!cascade(base, &base->tv4, (base->timer_jiffies>>26)&63)) )
    • 考虑每一次调用cascade函数的情况：它接收base的地址、base->tv2的地址、base->tv2中链表的索引作为参数。该索引值是通过观察base->timer_jiffies的特殊位上的值决定的。cascade()函数将base->tv2中链表上的所有动态定时器移动base->tv1的适当链表上。然后，如果所有base->tv2中链表不为空，它返回一个正值。如base->tv2中的链表为空，cascade()将再次被调用，把base->tv3中的某个链表上包含的定时器填充到base->tv2上，如此等等。
  • 使base->timer_jiffies的值加1。
  • 对于base->tv1.vec[index]链表上的每一个定时器，执行它所对应的定时器函数。特别说明的时，链表上的每个timer_list元素t实质上执行以下步骤。
    • t从base->tv1的链表中删除
    • 在多处理器系统上，将base->running_timer设置为&t
    • 设置t.base为NULL
    • 释放base->lock自旋锁，并允许本地中断
    • 传递t.data作为参数，执行定时器函数t.function
    • 获得base->lock自旋锁，禁止本地中断
    • 如果有其他定时器，则继续执行
  • 链表上的所有定时器已经被处理。继续执行最外层while循环的下一次循环。
• 最外层的while循环结束，这就意味着所有到期的定时器已经被处理了。在多处器系统中，设置base->running_timer为NULL
• 释放base->lock自旋锁并允许本地中断。

由于jiffies和timer_jiffies的值经常是一样的，所以最外层的while循环常常只执行一次。一般情况下，最外层循环会连续执行jiffies-base->timer_jiffies+1次。此外，如果在run_timer_softirq()正在执行时发生了时钟中断，那么也得考虑在这个节拍所出现的到期动态定时器，因为jiffies变量的值是由全局时钟中断处理程序异步增加的。

请注意，就在进入最外层循环前，run_timer_softirq()要禁止中断并获取base->lock自旋锁；调用每个动态定时器函数前，激活中断并释放自旋锁，直到函数执行结束，这就保证了动态定时器的数据结构不被交错执行的内核控制路径所破坏。

综上所述可知，这种相当复杂的算法确保了极好的性能。让我们来看看为什么，为了简单起见，假定TIMER_SOFTIRQ软中断正好在相应的时钟中断发生后执行。那么，在256次中出现的255次时钟中断，run_imter_softirq()仅仅运行到期定时器的函数，为了周期性地补充base->tv1.vec，在64次补充当中，63次足以把base->tv2指向的链表分成base->tv1指向的256个链表。依次地，base->tv2.vec数组必须在0.006%的情况下得到补充，即使16.4秒一次。类似地，每17分28秒补充一次base->tv3.vec，每18小时38分补充一次base->tv4.vec，而base->tv5.vec不需要补充。

动态定时器应用之一：nanosleep()系统调用

让我们考虑nanosleep()系统调用的服务例程，即sys_nanosleep()，它接收一个指向timespec结构的指针作为参数，并将调用进程挂起直到特定的时间间隔用完。服务例程首先调用copy_from_user()将包含在timespec结构中的值复制到局部变量t中，接着函数执行：

1
2

current->state = TASK_INTERRUPTIBLE;
remaining = schedule_timeout(timespec_to_jiffies(&t) + 1);

timespec_to_jiffies()函数将存放在timespec结构中的时间间隔转换成节拍数。内核使用动态定时器实现进程的延时。他们出现在schedule_timeout()中，执行：

1
2
3
4
5
6
7
8
9
10
11

struct timer_list timer;
unsigned long expire = timeout + jiffies;
init_timer(&timer);
timer.expires = expire;
timer.data = (unsigned long) current;
timer.function = process_timeout;
add_timer(&timer);
schedule(); //进程挂起直到定时器到时
del_singleshot_timer_sync(&timer);
timeout = expire - jiffies;
return (timeout < 0 ? 0 : timeout);

当schedule()被调用时，选择另一个进程执行；当前一个进程恢复执行时，该函数就删除这个动态定时器。最后的返回值有两种可能，0表示延迟到期，timeout表示如果进程因某些其他原因被唤醒，到延时到期还剩余的节拍数，延时到期时执行下列函数：

1
2
3

void process_timeout(unsigned long __data) {
	wake_up_process((task_t *)__data);
}

process_timeout()接收进程描述符指针作为参数，挂起的进程被唤醒。进程被唤醒就继续执行sys_nanosleep()，如果schedule_timeout()返回值表明进程延时到期，系统调用结束。

延迟函数

动态定时器有很大的设置开销和一个相当大的最小等待时间（1ms），所以使用很不方便，在这种情况下内核使用udelay()和ndelay()，前者接收一个微秒级时间间隔作为参数，并在指定的延迟结束后返回，后者与前者类似，但是指定延迟的参数时纳秒级的。

1
2
3
4
5
6
7
8
9
10

void udelay(unsigned long usecs) {
	unsigned long loops;
	loops = (usecs*HZ*current_cpu_data.loops_per_jiffy)/1000000;
	cur_time->delay(loops);
}
void ndelay(unsigned long nsecs) {
	unsigned long loops;
	loops = (nsecs*HZ*current_cpu_data.loops_per_jiffy)/1000000000;
	cur_time->delay(loops);
}

两个函数都依赖于cur_timer定时器对象的delay方法，它接收loops中的时间间隔作为参数。不过每一次loop精确的持续时间取决于cur_timer涉及的定时器对象。

• 如果cur_timer指向timer_hpet，timer_pmtmr和timer_tsc对象，那么一次loop对应于一个CPU循环，也就是两个连续CPU时钟信号间的时间间隔；
• 如果cur_timer指向对象，那么一次loop对应于一条紧凑指令循环在一次单独的循环中所花费的时间；

在初始化阶段，select_timer()设置好cur_timer后，内核通过执行calibrate_delay()函数来决定一个节拍里有多少次loop。这个值被保存在current_cpu_data.loops_per_jiffy变量中，这样udelay()和ndelay()就能根据它来把微秒和纳秒转换成loops。

当然，如果可以利用HPET或TSC硬件电路，那么cur_timer->delay()方法使用它们来获得精确的时间测量。否则，该方法执行一个紧凑指令循环的loops次循环。

与定时测量相关的系统调用

time() 和 gettimeofday() 系统调用

用户态下的进程通过以下几个系统调用获得当前的时间和日期。

• time()返回从1970年1月1日午夜（UTC）开始走过的秒数。
• gettimeofday()返回从 UTC 开始所走过的秒数及在前 1 秒内走过的微妙数，存放于timeval中。

gettimeofday()由sys_gettimeofday()实现，该函数调用do_gettimeofday()，它执行下列动作：

• 为读操作获取xtime_lock顺序锁。
• usec = cur_timer->getoffset();确定自上一次时钟中断以来走过的微妙数。
  • cur_timer可能指向对象timer_hpet、timer_pmtmr、timer_tsc、timer_pit，分别获取相应计数器的当前值与上一次时钟中断处理程序时的值比较。
• 如果某定时器中断丢失，usec += (jiffies - wall_jiffies) * 1000;，usec加上相应的延迟。
• usec += (xtime.tv_nsec / 1000);为 usec 加上前 1 秒内走过的微妙数。
• 将xtime的内容复制到系统调用参数tv指定的用户空间缓冲区中，并给微秒字段的值加上usec：tv->tv_sec = xtime->tv_sec; tv->tv_usec = usec;
• 在xtime_lock顺序锁上调用read_seqretry()，如果另一条内核控制路径同时为写操作获得了xtime_lock，跳回步骤 1。
• 检查微秒字段是否溢出，如果有必要调整该字段和秒字段：

1
2
3
4

while(tv->tv_usec >= 1000000){
	tv->tv_usec -= 1000000;
	tv->tv_sec++;
}

adjtimex() 系统调用

通常把系统配置成能在常规基准上运行时间同步协议，如网络定时协议（NTP），在每个节拍逐渐调整时间。这依赖于adjtimex()。adjtimex()接收指向timex结构的指针作为参数，用timex自动中的值更新内核参数，并返回具有当前内核值的同一结构。update_wall_time_one_tick()使用这以内核值对每个节拍中加到`xtime.tv_usec``的微秒进行微调。

setitimer() 和 alarm() 系统调用

Linux允许用户态的进程激活一种叫做间隔定时器的特殊定时器。它引起 Unix 信号被周期性地发送到进程，也可能在指定的延时后仅发送一个信号，它由以下两个方面来刻画：

• 发送信号所需要的频率
• 在下一个信号被产生以前所剩余的时间

setitimer()可激活间隔定时器，第一个参数指定应当采取下面哪一个策略：

• ITIMER_REAL，真正过去的时间，进程接收SIGALRM信号。
• ITIMER_VIRTUAL，进程在用户态下花费的时间，进程接收SIGVTALRM信号。
• ITIMER_PROF，进程既在用户态下又在内核态下所花费的时间，进程接收SIGPROF信号。

间隔定时器既能一次执行，也能周期循环。setitimer()的第二个参数指向一个itimerval类型的结构，它指定了定时器初始的持续时间以及定时器被重新激活后使用的持续时间。setitimer()的第三个参数是一个指针，可选，指向一个itimerval类型的结构，系统调用将先前定时器的参数填充到该结构中。

为分别实现前述每种策略的定时器，进程描述符包含 3 对字段：

• it_real_incr、it_real_value
• it_virt_incr、it_virt_value
• it_prof_incr、it_prof_value

每对中的第一个字段存放两个信号之间以节拍为单位的间隔，第二个字段存放定时器当前值。

ITIMER_REAL间隔定时器利用动态定时器实现，因为即使进程不运行，内核也能向其发送信号。每个进程描述符包含一个叫real_timer的动态定时器对象。

setitimer()过程：

• 初始化real_timer字段
• 调用add_timer()将动态定时器插入到合适的链表中
• 定时器到期时，内核执行it_real_fn()函数，并由it_real_fn()函数向进程发送一个SIGALRM信号
• 如果it_real_incr不为空，再次设置expires字段，并重新激活定时器

ITIMER_VIRTUAL、ITIMER_PROF间隔定时器不需要动态定时器，因只有进程运行时才会被更新。account_it_virt()、account_it_prof()被update_process_times()调用，而update_process_times()在单处理器系统上被 PIT 的时钟中断处理程序调用，在多处理器上被本地时钟中断处理程序调用。因此，每个节拍中，这两个间隔定时器都会被更新一次，如果到期，就给当前进程发送一个合适的信号。

alarm()会在一个指定的时间间隔用完时向调用的进程发送一个SIGALRM信号，参数为ITIMER_REAL时类似于setitimer()。

与 POSIX 定时器相关的系统调用

引入一种新型软定时器，尤其是针对多线程和实时应用程序。这些定时器被称为POSIX定时器。执行POSIX定时器必须向用户态程序提供一些POSIX时钟，也就是说虚拟时间源预定义了分辨度和属性。只要想使用POSIX定时器，就创建一个新的定时器资源并指定一个现存的POSIX时钟来作为定时基准。

Linux 2.6 内核提供两种类型的 POSIX 时钟：

• CLOCK_REALTIME，该虚拟时钟表示系统的实时时钟，本质上是xtime变量的值。clock_getres()系统调用返回的分辨度为 999 848ns，1s 内更新 xtime 约 1000 次。
• CLOCK_MONOTONIC，该虚拟时钟表示由于与外部时间源的同步，每次回到初值的系统实时时钟。实际上，该虚拟时钟由xtime和wal_to_monotonic两个变量的和表示。分辨度由clock_getres()返回，为 999 848ns。

Linux 内核使用动态定时器实现 POSIX 定时器，与ITIMER_REAL间隔定时器相似，但更灵活、可靠，区别如下：

• 一个 POSIX 定时器到期时，内核可以发送各种信号给整个多线程应用程序，也可发送给单个指定线程。
• 对于 POSIX 定时器，进程可调用timer_getoverrun()系统调用来得到自第一个信号产生以来定时器到期的次数。

进程调度

调度策略

传统 Unix 操作系统的调度必须实现几个冲突的目标：进程响应时间尽可能快，后台作业的吞吐量尽可能高，尽可能避免进程的饥饿现象，低优先级和高优先级的进程需要尽可能调和等等。调度策略是决定什么时候以怎样的方式为一个新进程选择运行的规则。

Linux 的调度基于分时技术，多个进程以时间多路复用方式运行，CPU的时间被分成片，给每个可运行进程分配一片。如果片到期，进程切换就可以执行。调度策略也根据进程的优先级对它们进行分类。Linux 中，进程的优先级是动态的。

• 进程分类方式一：
  • I/O 受限。频繁使用 I/O 设备，并花费很多时间等待 I/O 操作的完成。
  • CPU 受限。需要大量 CPU 时间的数值计算应用程序。
• 进程分类方式二：
  • 交互式进程。如命令 shell，文本编辑程序及图形应用程序。
  • 批处理进程。如程序设计语言的编译程序。
  • 实时进程。如视频和音频应用程序、机器人控制程序及从物理传感器收集数据的程序。

一个批处理进程可能是 I/O 受限的（如数据库服务器），或 CPU 受限的（如图像绘制程序）。Linux 中，调度程序可确认实时程序，通过基于进程过去行为的启发式算法（平均睡眠时间）区分交互式程序和批处理程序。通过下表中的系统调用改变调度优先级：

进程的抢占

如果进程进入TASK_RUNNING状态，内核检查到它的动态优先级大于当前正在运行进程的优先级，current的执行被中断，调度程序选择另一个进程运行（通常为刚刚变为可运行的进程）。

进程当前的时间片到期也可以被抢占。此时，当前进程thread_info结构中的TIF_NEED_RESCHED标志被设置，以便时钟中断处理程序终止时调度程序被调用。被抢占的进程没有被挂起，因为还处于TASK_RUNNING状态，只不过不再使用 CPU。

一个时间片必须持续多长？

如果平均时间片太短，进程切换引起的系统额外开销就变得非常高。如果平均时间片太长，进程看起来就不再是并发执行，也会降低系统的响应能力。Linux 单凭经验的方法，即选择尽可能长、同时能保持良好响应时机的一个时间片。

调度算法

Linux 2.6 的调度算法较好的解决了与可运行进程数量的比例关系，因为它在固定的时间内（与可运行的进程数量无关）选中要运行的队列，也很好地处理了与处理器数量的比例关系，因为每个CPU都拥有自己的可运行进程队列，较好的解决了区分交互式进程和批处理进程的问题。

总是至少有个一个可运行进程，即swapper进程，它的PID为0，只有在没有其他进程执行时运行。

每个 Linux 进程总是按照如下调度类型被调度：

• SHED_FIFO，先进先出的实时进程。当调度程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。如果没有更高优先级的实时进程，则进程继续使用CPU。
• SCHED_RR，时间片轮转的实时进程。把该进程的描述符放在运行队列链表的末尾。
• SCHED_NORMAL，普通的分时进程。

普通进程的调度

每个普通进程都有静态优先级：100（最高）~ 139（最低）。值越大静态优先级越低。新进程继承父进程的静态优先级，但可通过将某些nice值传递给nice()和setpriority()改变。

基本时间片

静态优先级本质上决定了进程的基本时间片，即进程用完了以前的时间片，系统分配给进程的时间片长度。静态优先级和基本时间片的关系如下：

静态优先级越小，基本时间片就越长，通常优先级越高的进程获得更长的CPU时间片。

动态优先级和平均睡眠时间

动态优先级的范围为：100（最高）~ 139（最低），它是调度程序在选择新进程来运行的时候使用的优先级：动态优先级 = max(100, min( 静态优先级 - bonus + 5, 139))。bonus的值与进程的平均睡眠时间相关，范围0~10，小于5表示降低动态优先级以示惩罚，大于5表示增加动态优先级以示奖赏。

粗略地将，平均睡眠时间是进程在睡眠状态所消耗的平均纳秒数，进程在运行的过程中平均睡眠时间递减，不会大于 1s。

平均睡眠时间也被调度程序用来判断一个给定进程是交互进程还是批处理进程。如果一个进程满足下式，则被看作交互式进程：动态优先级 ≤ 3 × 静态优先级 / 4 + 28，相当于下面的：bonus - 5 ≥ 静态优先级 / 4 - 28。

表达式：静态优先级/4-28被称为交互式的δ。应该注意，高优先级进程比低优先级进程更容易成为交互式进程。例如，具有最高静态优先级（100）的进程，当它的bonus值超过2，即睡眠时间超过200ms时，就被看作是交互式进程。相反，具有最低静态优先级（139）的进程决不会被当作交互式进程，因
为bonus值总是小于11，相应地需要交互式δ等于6。一个具有缺省静态优先级（120）的进程，一但其平均睡眠时间超过700ms，就成为交互式进程。

活动和过期进程

当一个较高优先级的进程用完其时间片，应该被还没有用完时间片的低优先级进程取代，为此，调度程序维持两个不相交的可运行进程的集合。

• 活动进程：还没有用完时间片的进程，允许运行。
• 过期进程：用完了时间片，被禁止运行，直到所有活动进程过期。

总体方案要稍复杂一些：

• 用完时间片的活动批处理进程总是变成过期进程。
• 用完时间片的交互式进程仍是活动进程：调度重新重填其时间片并把它留在活动进程集合中。
• 当最老的过期进程等待了很久，或过期进程比交互式进程的静态优先级高，调度程序把用完时间片的交互式进程移到过期进程集合。
• 活动进程集合最终会变为空，过期进程将有机会运行。

实时进程的调度

每个实时进程都有实时优先级，范围 1（最高）~ 99（最低）。调度程序总是让优先级高的进程运行，实时进程运行的过程中禁止低优先级进程的运行。实时进程总是被当成活动进程。用户可通过sched_setparam()和sched_setscheduler()改变进程的实时优先级。

只有如下事情发生，实时进程才会被另一个进程取代：

• 进程被另外一个具有更高优先级的实时进程抢占。
• 进程执行了阻塞操作并进入睡眠（处于TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE状态）。
• 进程停止（处于TASK_STOPPED或TASK_TRACED状态）或被杀死（处于EXIT_ZOMBIE或EXIT_DEAD状态）。
• 进程通过调用sched_yield()自愿放弃 CPU。
• 进程是基于时间片轮转的实时进程（SCHED_RR)，且用完了时间片。

当系统调用nice()和setpriority()用于基于时间片轮转的实时进程时，不改变实时进程的优先级而会改变其基本时间片的长度。

调度程序所使用的数据结构

进程链表链接所有的进程描述符，运行队列链表链接所有的可运行进程（处于TASK_RUNNING状态的进程）的进程描述符，swapper 进程（idle 进程）除外。

数据结构 runqueue

runqueue结构存放在runqueues每 CPU 变量中。宏this_rq()产生本地 CPU 运行队列的地址，宏cpu_rq(n)产生索引为n的 CPU 运行队列的地址。

最重要的字段是与可运行进程的链表相关的字段。系统中的每个可运行进程属于且只属于一个运行队列。只要可运行进程保持在同一个运行队列，它就只可能在拥有该运行队列的CPU上执行。

arrays是一个包含两个prio_array_t的数组，每个数据结构都表示一个可运行进程的集合。两个数据结构的作用会发生周期性的变化：活动进程突然变成过期进程，过期进程变为活动进程。调度程序简单地交换运行队列的 active 和 expired 字段的内容完成这种变化。

进程描述符

每个进程描述符都包含几个与调度相关的字段。

新进程被创建时，copy_process()调用sched_fork()用下述方法设置current父进程和p子进程的time_slice字段：

1
2

p->time_slice = (current->time_slice + 1) >> 1;
current->time_slice >> = 1;

父进程剩余的节拍数被划分成两等份：一份给自己，另一份给子进程。避免因为创建过多子进程而占用太多时间片，一个进程不能通过创建多个后代来霸占资源。

如果父进程的时间片只剩下一个时钟节拍，则current->time_slice置为0。copy_process()把current-time_slice重新置为 1，然后调用scheduler_tick()递减该字段。

copy_process()也初始化子进程描述符中与进程调度相关的字段：

1
2

p->first_time_slice = 1;       // 因为子进程没有用完它的时间片，所以设置为 1
p->timestamp = sched_clock();  // 返回被转换成纳秒的 64 位仅存去 TSC 的内容

调度程序所使用的函数

调度程序依靠几个函数完成调度工作

• scheduler_tick()：维持当前最新的time_slice计数器
• try_to_wake_up()：唤醒睡眠进程
• recalc_task_prio()：更新进程的动态优先级
• schedule()：选择要被执行的新进程
• load_balance()：维持多处理器系统中运行队列的平衡

scheduler_tick()

主要步骤如下：

• 将转换为纳秒的 TSC 值存入本地运行队列的timestamp_last_tick字段。TSC值从sched_clock()获得。
• 如果进程是本地 CPU 的 swapper 进程，执行下列步骤：
  • 如果本地运行队列还包括另外一个可运行的进程，就设置当前进程的TIF_NEED_RESCHED字段，强制重新调度。
  • 跳到第 7 步（没必要更新 swapper 进程的时间片计数器）。
• 如果current->array没有指向本地运行队列的活动链表，说明进程已经过期但还没有被替换，则设置TIF_NEED_RESCHED标志，强制重新调度，跳到第 7 步。
• 获得this_rq()->lock自旋锁。
• 递减当前进程的时间片计数器，如果已经用完时间片，则根据进程的调度类型进行相应操作，稍后讨论。
• 释放this_rq()->lock自旋锁。
• 调用reabalance_tick()，保证不同 CPU 的运行队列的可运行进程数量基本相同。

更新实时进程的时间片

对于先进先出的实时进程，scheduler_tick()什么也不做，因为current不可能被其他低优先级或等优先级的进程抢占，维持最新时间片计数器没有意义。

对于基于时间片轮转的实时进程，scheduler_tick()递减其时间片计数器，如果时间片被用完，执行一系列操作以达到抢占当前进程的目的：

1
2
3
4
5
6
7

if(current->policy == SCHED_RR && !--current->time_slice){
	current->time_slice = task_timeslice(current);
	current->first_time_slice = 0;
	set_tsk_need_resched(current);
	list_del(&current->run_list);
	list_add_tail(&current->run_list, this_rq()->active->queue+current->prio); // 然后把进程重新插入到同一个活动链表的尾部
}

第一步操作包括调用task_timeslice()来重填进程的时间片计数器，根据进程的静态优先级返回相应的基本时间片。此外，current的first_time_slice字段被清零，该标志被fork()中的copy_process()设置，并在进程的第一个时间片刚一用完立即清0。

第二步，scheduler_tick()调用函数set_tsk_need_resched()设置进程的TIF_NEED_RESCHED标志，强制调用schedule()函数，使current被另一个具有相同或更高优先级的实时进程取代。

scheduler_tick()最后一步把进程描述符移到与当前进程优先级相对应的运行队列活动链表尾部。把current指向的进程放到链表尾部，保证在每个优先级与它相同的可运行实时进程获得CPU时间片以前，它不会再次运行。这是基于时间片的轮转，进程描述符的移动首先调用list_del()把进程从运行队列的活动链表中删除，之后调用list_add_tail()把进程重新插入到同一个活动链表尾部。

更新普通进程的时间片

如果当前进程是普通进程，scheduler_tick()执行如下操作：

• 递减时间片计数器（current->time_slice)
• 如果时间片用完，执行下列操作：
  • dequeue_task()从可运行进程的this_rq()->active集合中删除current
  • set_tsk_need_resched()设置TIF_NEED_RESCHED标志。
  • 更新current的动态优先级：current->prio = effective_prio(current);
    • effective_prio()读current的static_prio和sleep_avg字段，计算进程的动态优先级。
  • 重填进程的时间片：current->time_slice = task_timeslice(current);和current->first_time_slice = 0;
  • 如果本地运行队列的数据结构的expired_timestamp字段等于0（过期进程集合为空），把当前时钟节拍的值赋给expired_timestamp：
    • if(!this_rq()->expired_timestamp) this_rq()->expired_timestamp = jiffies;
  • 把当前进程插入活动进程集合或过期进程集合：

1
2
3
4
5
6
7
8
9
10

// 如果进程是一个非交互式进程，TASK_INTERACTIVE 宏产生值 0
// EXPIRED_STARVING 宏检查到运行队列中的第一个过期进程的等待时间已经超过 1000 个时钟节拍乘以运行队列中的可运行进程数加1，产生值 1
// 如果当前进程的静态优先级大于一个过期进程的静态优先级，EXPIRED_STARVING 宏也产生值 1
if(!TASK_INTERACTIVE(current) || EXPIRED_STARVING(this_rq()){  
	enqueue_task(current, this_rq()->expired);  // 插入过期进程集合
	if(current->static_prio < this_rq()->best_expired_prio)
		this_rq()->best_expired_prio = current->static_prio;
}
else
	enqueue_task(current, this_rq()->active);   // 插入活动进程集合

• 否则，时间片没有用完（current->time_slice不等于 0），检查当前进程的剩余时间片是否太长：

1
2
3
4
5
6
7
8

// bonus = TIMESLICE_GRANULARIT 宏产生的 CPU 的数量 * 比例常量 的乘积
// 具有高静态优先级的交互式进程，其时间片被分成大小为 TIMESLICE_GRANULARITY 的几个片段，以使这些进程不会独占 CPU
if(TASK_INTERACTIVE(p) && !((task_timeslice(p) - p->time_slice) % TIMESLICE_GRANULARIT(p)) && 
	(p->time_slice >= TIMESLICE_GRANULARITY(p)) && (p->array == rq->active)) {
	list_del(&current->run_list);
	list_add_tail(&current->run_list, this_rq()->active->queue+current->prio);
	set_tsk_need_resched(p);
}

try_to_wake_up()

通过将进程状态设置为TASK_RUNNING，并把该进程插入本地 CPU 的运行队列来唤醒睡眠或停止的进程。参数：

• 被唤醒进程的进程描述符p
• 可被唤醒的进程状态掩码state
• 标志sync，禁止被唤醒的进程抢占本地 CPU 上正在运行的进程

执行下列操作：

1. task_rq_lock()禁用本地中断，获得最后执行进程的 CPU 所拥有的运行队列rq的锁。CPU的逻辑号存储在p->thread_info->cpu字段。
2. 如果进程的状态p->state不属于参数state（状态掩码），跳到第 9 步，终止函数。
3. 如果p->array != NULL，那么进程已经属于某个运行队列，跳到第 8 步。
4. 多处理器系统中，检查要被唤醒的进程是否应该迁移到另一个 CPU 的运行队列，根据以下启发式规则选择一个目标运行队列：
   1. 空闲 CPU 的运行队列。
   2. 先前工作量较小的 CPU 运行队列。
   3. 如果进程最近被执行过，选择老的运行队列 。
   4. 工作量较小的本地 CPU 运行队列。
5. 如果进程处于TASK_UNINTERRUPTIBLE状态，递减目标运行队列的nr_uninterruptible字段，p->activeted = -1。
6. 调用activate_task()，执行下列步骤：
   1. sched_clock()获得以纳秒为单位的当前时间戳。如果目标 CPU 不是本地 CPU，补偿本地时钟中断的偏差：now = (sched_clock() - this_rq()->timestamp_last_tick) + rq->timestamp_last_tick;
   2. recalc_task_prio()，参数为进程描述符指针、上一步计算出的时间戳now
   3. 根据情况设置p->activated字段。
   4. p->timestamp = now;
   5. 把进程描述符插入活动进程集合：enqueue_task(p, rq->active); rq->nr_running++;
7. 如果目标 CPU 不是本地 CPU，或没有设置sync标志，就检查可运行的新进程的动态优先级是否比rq运行队列中当前进程的动态优先级高，如果p->prio < rq->curr->prio，调用resched_task()抢占rq->curr。
   1. 单处理器系统中，resched_task()仅执行set_tsk_need_resched()设置rq->curr的TIF_NEED_RESCHED标志；
   2. 多处理器系统中，resched_task()如果发现TIF_NEED_RESCHED的旧值为0、目标CPU与本地CPU不同、rq->curr进程的TIF_POLLING_NRFLAG的标志清0，调用smp_send_reschedule()产生 IPI，强制目标 CPU 重新调度。
8. 把进程的p->state置为TASK_RUNNING。
9. task_rq_unlock()打开rq运行队列的锁并打开本地中断。
10. 成功唤醒进程返回 1，否则返回 0。

recalc_task_prio()

更新进程的平均睡眠时间p->sleep_avg和动态优先级p->prio。参数：

• 进程描述符的指针p
• 由sched_clock()计算出的当前时间戳now

执行下述操作：

1. 把min(now - p->timestamp, 10^9);的结果赋值给sleep_time。p->timestamp包含导致进程进入睡眠状态的进程切换的时间。因此sleep_time是进程从最后一次执行开始，消耗在睡眠状态的纳秒数
2. 如果sleep_time不大于0，不需要更新进程的平均睡眠时间，跳到第 8 步。
3. 如果进程不是内核线程、从TASK_UNINTERRUPTIBLE状态被唤醒（p->activated等于-1）、连续睡眠的时间超过睡眠极限，则p->sleep_avg设置为相当于900时钟节拍的值，然后跳到第 8 步。
4. 执行CURRENT_BONUS宏计算进程原来的平均睡眠时间的bonus值，如果10 - bonus大于0，函数用这个值与sleep_time相乘。因为将要把sleep_time加到进程的平均睡眠时间上，所以当前平均睡眠时间越短，它增加的就越快。
5. 如果进程处于TASK_UNINTERRUPTIBLE状态但不是内核线程，执行下述步骤：
   1. 如果平均睡眠时间p->sleep_avg大于睡眠时间极限，sleep_time置为0，不用调整平均睡眠时间，跳到第 6 步。
   2. 如果sleep_time + p->sleep_avg大于等于睡眠时间极限，p->sleep_avg置为睡眠时间极限并把sleep_time置为0。
   3. 通过对进程平均睡眠时间的轻微限制，函数不会对睡眠时间长的批处理进程给予过多奖赏。
6. 把sleep_time加到平均睡眠时间p->sleep_avg上。
7. 检查p->sleep_avg是否超过1000个以纳秒为单位的时钟节拍，如果是，函数就把p->sleep_avg减到1000个时钟节拍。
8. 更新进程的动态优先级：p->prio = effective_prio(p)

schedule()

schedule()实现调度程序。从运行队列链表中找到一个进程，并随后将 CPU 分配给这个进程。schedule()可由几个内核控制路径调用，可采取直接调用或延迟调用的方式。

直接调用

如果current进程未获得必需的资源而阻塞，就直接调用调度程序。要阻塞的内核路径执行下述步骤：

1. 把current进程插入适当的等待队列。
2. 把current进程的状态改为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。
3. 调用schedule()。
4. 如果资源不可用，跳到第 2 步；否则，从等待队列中删除current进程。
5. 一旦资源可用，就从等待队列中删除current进程

延迟调用

也可以把current进程的TIF_NEED_RESCHED标志置为1，而以延迟方式调用调度程序。每次在恢复用户进程的执行之前会检查该标志。延迟调用调度程序的例子：

• current进程用完时间片，由scheduler_tick()完成schedule()的延迟调用。
• 被唤醒进程的优先级高于当前进程，try_to_wake_up()完成schedule()的延迟调用。
• 发出系统调用sched_setscheduler()时。

进程切换前schedule()所执行的操作

schedule()的任务是用另一个进程来替换当前正在执行的进程，关键是设置一个叫做next的变量，它指向被选中的进程，以取代current进程。
如果系统中没有优先级高于current进程的可运行进程，那么next与current相等，不发生进程切换。

schedule()首先禁用内核抢占，初始化一些局部变量：

1
2
3
4

need_resched:
preempt_disable();
prev = current;    
rq = this_rq();

把current返回的指针赋给prev，并把与本地 CPU 对应的运行队列赋给rq。

下一步current()保证prev不占用大内核锁：

1
2

if(prev->lock_depth >= 0)
	up(&kernel_sem);

调用sched_clock()获取TSC，将其值转换为纳秒，存放在now中。然后计算prev所用的CPU时间片长度。通常使用限制在1s内的时间。

1
2
3
4

now = sched_clock();
run_time = now - prev->timestamp;
if(run_time > 1000000000)
	run_time = 1000000000;  // 限制在 1s

优待有较长平均睡眠时间的进程：

1

run_time /= (CURRENT_BONUS(pre) ? : 1);

寻找可运行进程前，schedule()必须关掉本地中断，并获得所要保护的运行队列的自旋锁：

1

spin_lock_irq(&rq->lock);

prev可能是一个正在被终止的进程，schedule()通过检查PF_EDAD标志验证：

1
2

if(prev->flags & PF_DEAD)
	prev->state = EXIT_DEAD;

接下来schedule()检查prev的状态。如果不是可运行状态，且没有在内核态被抢占，就从运行队列删除prev进程。但是，如果它有非阻塞挂起信号，且状态为TASK_INTERRUPTIBLE，将该进程的状态设置为TASK_RUNNING，并插入运行队列，给prev一次被选中执行的机会：

1
2
3
4
5
6
7
8
9
10

if(prev->state != TASK_RUNNING && !(preempt_count() & PREEMPT_ACTIVE))
{
	if(prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))
		prev->state = TASK_RUNNING;
	else {
		if(prev->state == TASK_UNINTERRUPTIBLE)
			rq->nr_uninterruptible++;
		deactivate_task(prev, rq);
	}
}

deactivate_task()从运行队列中删除该进程：

1
2
3

rq->nr_running--;
dequeue_task(p, p->array);
p->array = NULL;

现在，schedule()检查运行队列中剩余的可运行进程数。如果有可运行的进程，就调用dependent_sleeper()，绝大多数情况下，该函数立即返回 0。但是，如果内核支持超线程技术，如果被选中执行的进程优先级比已经在相同物理 CPU 的某个逻辑 CPU 上运行的兄弟进程低，则schedule()拒绝选择该进程，而执行swapper进程：

1
2
3
4
5
6
7
8

if(rq->nr_running)
{
	if(dependent_sleeper(smp_processor_id(), rq))
	{
		next = rq->idle;
		goto switch_tasks;
	}
}

如果运行队列中没有可运行的进程，则调用idle_balance()从另外一个运行队列迁移一些可运行进程过来。

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

if(!rq->nr_running)
{
	idle_balance(smp_processor_id(), rq);
	if(!rq->nr_running)
	{
		next = rq->idle;
		rq->expired_timestamp = 0;
		wake_sleeping_dependent(smp_processor_id(), rq);
		if(!rq->nr_running)
			goto switch_tasks;
	}
}

如果idle_balance()没有迁移成功，当内核支持超线程技术时，schedule()调用wake_sleeping_dependent()重新调度空闲CPU的可运行进程。然而，在单处理器系统中，迁移失败时，将swapper进程作为next进程。

假设运行队列中有可运行进程，现在检查这些可运行进程中是否至少有一个进程是活动的。如果没有，则交换运行队列结构的active和expired字段。

1
2
3
4
5
6
7
8
9

array = rq->active;
if(!array->nr_active)
{
	rq->active = rq->expired;
	rq->expired = array;
	array = rq->active;
	rq->expired_timestamp = 0;
	rq->best_expired_prio = 140;
}

现在可在活动prio_array_t中搜索一个可运行的进程了。首先schedule()搜索进程集合掩码的第一个非0位，其下标对应包含最佳运行进程的链表。随后，返回该链表的第一个进程描述符：

1
2

idx = sched_find_first_bit(array->bitmap);
next = list_entry(array->queue[idx].next, task_t, run_list); 

sched_find_first_bit()基于bsfl汇编指令，返回 32 位数组中被设置为 1 的最低位的位下标。next存放将取代prev的进程描述符指针。

schedule()检查next->activated字段，表示进程被唤醒时的状态。

如果next是一个普通进程，正在从TASK_INTERRUPTIBLE或TASK_STOPPED状态被唤醒，调度程序就把自从进程插入运行队列开始所经过的纳秒数加到进程的平均睡眠时间中。

1
2
3
4
5
6
7
8
9
10
11

if(next->prio >= 100 && next->activated > 0)
{
	unsigned long long delta = now - next->timestamp;
	if(next->activated == 1)
		delta = (delta * 38) / 128;
	array = next->array;
	dequeue_task(next, array);
	recalc_task_prio(next, next->timestamp + delta);
	enqueue_task(next, array);
}
next->activated = 0;

schedule()进行进程切换时所执行的操作

schedule()已经要让next进程运行，内核将立刻访问next进程的thread_info，其地址存放在next进程描述符接近顶部的位置。

1
2

switch_tasks:
prefetch(next);

在替代 prev 前，调度程序应该完成一些管理的工作，以防以延迟方式调用schedule()，clear_tsk_need_resched()清除prev的TIF_NEED_RESCHED标志。然后函数记录CPU正在经历静止状态。

1
2

clear_tsk_need_resched(prev);
rcu_qsctr_inc(prev->thread_info->cpu);  // CPU 正在经历静止状态

schedule()必须减少prev的平均睡眠时间，并把它补充给进程所使用的CPU时间片，随后更新进程的时间戳：

1
2
3
4

prev->sleep_avg -= run_time;
if((long)prev->sleep_avg <= 0)
	prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;

prev和next可能是同一个进程，这时函数不作进程切换：

1
2
3
4
5

if(prev == next)
{
	spin_unlock_irq(&rq->lock);
	goto finish_schedule;
}

否则，进程切换：

1
2
3
4

next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
prev = context_switch(rq, prev, next);

context_switch()建立next的地址空间。进程描述符的active_mm字段指向进程所使用的内存描述符，而mm字段指向进程所拥有的内存描述符。对于一般进程，这两个字段地址相同；而内核线程没有自己的地址空间，mm总是被置为 NULL。context_switch()确保，如果next是一个内核线程，使用prev所使用的地址空间：

1
2
3
4
5
6

if(!next->mm)  // 内核线程
{
	next->active_mm = prev->active_mm;
	atomic_inc(&prev->active_mm->mm_count);
	enter_lazy_tlb(prev->active_mm, next);
}

如果内核线程都有自己的地址空间，当调度程序选择一个新进程运行时，需改变页表，因为内核线程仅使用线性地址空间的第 4 个 GB，该空间的映射对系统的所有进程都是相同的。甚至在最坏情况下，写cr3寄存器会使所有TLB表项无效，导致极大的性能损失。现在的Linux中，如果next是内核线程，就不触及页表，进一步优化，schedule()将进程设置为懒惰TLB模式。而如果next是一个普通进程，context_switch()用next的地址空间替换prev的地址空间：

1
2

if(next->mm)  // 普通进程
	switch_mm(prev->active_mm, next->mm, next);

如果prev是内核线程或正在退出的进程，context_switch()把prev内存描述符的指针保存到运行队列的prev_mm字段中：

1
2
3
4
5

if(!prev->mm)
{
	rq->prev_mm = prev->active_mm;
	prev->active_mm = NULL;
}

现在，context_switch()可调用switch_to()执行prev和next之间的进程切换了：

1
2

switch_to(prev, next, prev);
return prev;

总结：更新prev的时间片、时间戳，根据prev是内核线程还是普通线程，进行相应的内存描述符替换。

进程切换后 schedule() 所执行的动作

sechedule()函数中在switch_to宏后紧接着的指令不是让next进程立即执行，而是如果稍后调度程序又选择prev时由prev执行。到那时，prev不指向schedule()开始时所替换出的进程，而是指向被调度时被prev替换出的进程。

进程切换后的第一部分指令：

1
2

barrier();  // 代码优化屏障
finish_task_switch(prev);

1
2
3
4
5
6
7
8

mm = this_rq()->prev_mm;
this_rq()->prev_mm = NULL;
prev_task_flags = prev->flags;
spin_unlock_irq(&this_rq()->lock);
if(mm)
	mmdrop(mm);
if(prev_task_flags & PF_DEAD)
	put_task_struct(prev);

schedule()的最后一部分指令：

1
2
3
4
5
6
7
8
9

finish_schedule:

prev = current;
if(prev->lock_depth >= 0)
	__reacquire_kernel_lock();
preempt_enable_no_resched();
if(test_bit(TIF_NEED_RESCHED, &current_thread_info()->flags)
	goto need_resched;
return;  

多处理器系统中运行队列的平衡

关注三种不同类型的多处理机器：

• 标准的多处理器体系结构：所共有的RAM被所有CPU共享
• 超线程：超线程芯片是一个立刻执行几个执行线程的微处理器，它包括几个内部寄存器的拷贝，并快速在它们之间切换。当前线程在访问内存的间隙，处理器可以执行另一个线程
• NUMA：把CPU和RAM以本地节点分组。CPU访问与它在同一个节点的本地RAM时几乎没有竞争，但是访问远程RAM时，芯片就非常慢。

一个保持可运行状态的进程通常被限制在一个固定的CPU上，这样可以填满CPU的硬件高速缓存，但是这可能引起严重的性能损失。内核应周期性地检查运行队列的工作量是否平衡，需要时，把一些进程从一个运行队列迁移到另一个运行队列。为适应各种已有的多处理器体系结构，Linux 提出一种基于调度域概念的复杂的运行队列平衡算法。

调度域

调度域实际上是一个CPU集合，它们的工作量由内核保持平衡。调度域采取分层组织的形式：最上层的调度域包括多个子调度域，每个子调度域包括一个CPU子集。每个调度域被划分为一个或多个组，每个组代表调度域的一个CPU子集，工作量的平衡在调度域的组之间完成。只有在一个组的工作量远远大于另一个组时才把进程从一个CPU调度到另一个CPU。

每个调度域由sched_domain描述符表示，调度域中的每个组由sched_group描述符表示。sched_domain的groups字段指向组描述符链表中的第一个元素。sched_domain的parent字段指向父调度域的描述符。

所有物理CPU的sched_domain描述符存放在每CPU变量phys_domains中。

• 如果内核不支持超线程技术，这些域在域层次结构的最底层，运行队列描述符的sd字段指向它们。
• 如果内核支持超线程技术，底层调度域存放在每CPU变量cpu_domains中。

rebalance_tick()

为了保持系统中运行队列的平衡，每经过一次时钟节拍，scheduler_tick()调用rebalance_tick()。参数有：

• 本地CPU的下标this_cpu
• 本地运行队列的地址this_rq

• 标志idle

  • SCHED_IDLE，CPU当前空闲，即current是swapper进程
  • NOT_IDLECPU当前不空闲，即current不是swapper进程

• 首先，访问运行队列描述符的nr_running和cpu_load字段，确定运行队列中的进程数，更新运行队列的平均工作量。

• 然后，从基本域到最上层的调度域循环，每次循环确定是否已到调用load_balance()的时间，从而在调度域上指向重新平衡的操作。
  • sched_domain的idle值决定调用load_balance()的频率。
  • 如果idle等于SCHED_IDLE，那么运行队列为空，load_balance()被调用频率高。
  • 反之，如果idle等于NOT_IDLE，load_balance()被调用频率低。

load_balance()

检查调度域是否处于严重的不平衡状态，如果是，从最繁忙的的组中迁移一些进程到本地CPU的运行队列。参数有：

• this_cpu，本地 CPU 的下标
• this_rq，本地运行队列的描述符的地址
• sd，指向被检查的调度域的描述符
• idle，取值为SCHED_IDLE或NOT_IDLE

函数执行下面的操作：

1. 获取this_rq->lock自旋锁。
2. find_busiest_group()分析调度域中各组的工作量。返回最繁忙的sched_group描述符的地址，假设该组不包括本地CPU，在这种情况下，还返回为恢复平衡而被迁移到本地运行队列中的进程数。如果最繁忙的组包括本地CPU，或所有的组本来就是平衡的，返回NULL。需过滤统计工作量中的波动。
3. 如果find_busiest_group()在调度域中没有没有找到既不包括本地CPU又非常繁忙的组，就释放this_rq->lock自旋锁，调整调度域描述符的参数，以延迟本地CPU下一次对load_balance()的调度，然后函数终止。
4. find_busiest_queue()查找第2步中找到的组中最繁忙的CPU，返回相应运行队列的描述符地址busiest。
5. 获取另一个自旋锁busiest->lock。为避免死锁，首先释放this_rq->lock，然后通过增加CPU下标获得这两个锁。
6. move_tasks()从最繁忙的运行队列把一些进程迁移到本地运行队列this_rq中。
7. 如果move_tasks()没有迁移成功，则调度域不平衡，busiest->active_balance = 1，并唤醒migration线程，其描述符存放在busiest->migration_thread中。migration内核下次顺着调度域的链搜索：从最繁忙运行队列的基本域到最上层域搜索空闲CPU，如果找到一个空闲CPU，就调用move_tasks()把一个进程迁移到空闲运行队列。
8. 释放busiest->lock和this_rq->lock自旋锁。
9. 函数结束。

move_tasks()

把进程从源运行队列迁移到本地运行队列。接收参数有：

• this_rq，本地运行队列描述符
• this_cpu，本地 CPU 下标
• busiest，源运行队列描述符
• max_nr_move，被迁移进程的最大数
• sd，在其中执行平衡操作的调度域的描述符地址
• idle标志，可被设置为SCHED_IDLE、NOT_IDLE、NEWLY_IDLE

函数首先分析busiest运行队列的过期进程，从优先级高的进程开始。扫描完所有的过期进程后，扫描busiest运行队列的活动进程，对所有后续进程调用can_migrate_task()，如果下列条件都满足，can_migrate_task()返回1：

• 进程当前没有在远程CPU上执行
• 本地CPU包含在进程描述符的cpus_allowed位掩码中
• 至少满足下列条件之一：
  • 本地 CPU 空闲。如果内核支持超线程技术，所有本地物理芯片中的逻辑 CPU 必须空闲。
  • 内核在平衡调度域是因反复迁移进程失败而现如困境。
  • 被迁移的进程不是“高速缓存命中”。

如果can_migrate_task()返回1，调用pull_task()将后续进程迁移到本地运行队列。pull_task()先执行dequeue_task()从远程运行队列删除进程，然后执行enqueue_task()把进程插入本地运行队列，如果刚被迁移的进程比当前进程拥有更高的动态优先级，调用resched_task()抢占本地CPU的当前进程。

与调度相关的系统调用

nice()

nice()允许进程改变自己的基本优先级。包含在increment参数中的整数值用来修改进程描述符的nice字段。nice()已被setpriority()取代。

getpriority() 和 setpriority()

nice()只影响调用它的进程，而getpriority()和setpriority()作用于给定组中所有进程的基本优先级。getpriority()返回20减去给定组中所有进程中最低nice字段的值，即最高优先级。setpriority()把给定组中所有进程的基本优先级设置为一个给定的值。

内核对这两个系统调用的实现基于sys_getpriority()和sys_setpriority()服务例程，参数有：

• which：指定进程组的值，采用以下值:
  • PRIO_PROCESS：根据进程ID选择进程（pid）
  • PRIO_PGRP：根据组ID先择进程（pgrp）
  • PRIO_USER：根据用户ID选择进程（uid）
• who：用pid、pgrp、uid的值选择进程
• niceval：新的基本优先级值

sched_getaffinity()和sched_setaffinity()

分别返回和设置CPU进程亲和力掩码，即允许执行进程的CPU的位掩码。该掩码存放在进程描述符的cpus_allowed字段中。

与实时进程相关的系统调用

sched_getscheduler()和sched_setscheduler()

sched_getscheduler()查询参数pid表示的进程当前使用的调度策略。如果pid等于0，检索调用进程的策略。如果成功，为进程返回策略：SCHED_FIFO、SCHED_RR或SCHED_NORMAL。

sched_setscheduler()既设置调度策略，也设置由参数pid表示的进程的相关参数。如果pid等于0，调用进程的调度程序参数将被设置。

sched_getparam()和sched_setparam()

sched_getparam()检索参数pid表示的进程的调度参数。如果pid是0，current`进程的参数被检索。

sched_setparam()类似于sched_setscheduler()，不同之处在于不让调用者设置policy字段。

sched_yield()

允许进程在不被挂起的情况下自愿放弃CPU，进程仍然处于TASK_RUNNING状态，但调度程序把它放在运行队列的过期进程集合中，或运行队列链表的末尾。

sched_get_priority_min()和sched_get_priority_max()

sched_get_priority_min()和sched_get_priority_max()分别返回最小和最大实时静态优先级的值，该值由policy参数标识的调度策略使用。

sched_rr_get_interval()

把参数pid标识的实时进程的轮转时间片写入用户地址空间的一个结构中。如果pid等于 0，系统调用就写当前进程的时间片。

绪论

Linux与其他类Unix内核的比较

在Linux系统下，很容易编译和运行目前现有的大多数Unix程序。Linux包括了现代Unix操作系统的全部特点，诸如虚拟存储、虚拟文件系统、轻量级进程、Unix信号量、SVR4进程间通信、支持对称多处理器系统等。

• 单块结构的内核：它是一个庞大、复杂的自我完善程序，由几个逻辑上独立的成分构成。大多数商用Unix变体也是单块结构。
• 编译并静态连接的传统Unix内核：大部分现代操作系统内核可以动态地装载和卸载部分内核代码，通常把这部分代码称作模块module。Linux对模块的支持是很好的。
• 内核线程：Linux以一种十分有线的方式使用内核线程来周期性地执行几个内核函数，但是它们并不代表基本的执行上下文抽象。
• 多线程应用程序支持：一个多线程用户程序由很多轻量级进程LWP组成，这些进程可能对共同的地址空间、共同的物理内存页、共同的打开文件等等进行操作。Linux把轻量级进程当做基本的执行上下文，通过非标准的clone()系统调用来处理它们。
• 抢占式preemptive内核：Linux可以随意交错执行处于特权模式的执行流。
• 多处理器支持：Linux支持不同存储模式的对称多处理，包括NUMA：系统不仅可以使用多处理器，而且每个处理器可以毫无区别地执行任何一个任务。
• 文件系统：Linux标准文件系统呈现出多种风格。

操作系统基本概念

操作系统必须完成两个主要目标：

• 与硬件部分交互，为包含在硬件平台上的所有低层可编程部件提供服务。
• 为运行在计算机系统上的应用程序（即所谓用户程序）提供执行环境。

现代操作系统依靠特殊的硬件特性来禁止用户程序直接与低层硬件部分进行交互，或者禁止直接访问任意的物理地址。硬件为CPU引入了至少两种不同的执行模式：用户程序的非特权模式和内核的特权模式。Unix把它们分别称为用户态User Mode和内核态Kernel Mode。

下面是一些基本概念:

• 多用户系统：一台能并发和独立地执行分别属于两个或多个用户的若干应用程序的计算机。
• 用户和组：每个用户用一个数字来表示，及用户标识符User ID，UID。每个用户是一个或多个用户组的一名成员，组由唯一的用户组标识符user group ID标识。root用户几乎无所不能。
• 进程：所有的操作系统都使用一种基本的抽象：进程process。一个进程可以定义为：程序执行时的一个实例，或者一个运行程序的执行上下文。Linux是具有抢占式进程的多处理操作系统。
• 内核体系结构：大部分Unix内核是单块结构：每一个内核层都被集成到整个内核程序中，并代表当前进程在内核态下运行。相反，微内核microkernel操作系统只需要内核有一个很小的函数集。运行在微内核之上的几个系统进程实现从前操作系统级实现的功能，如内存分配程序、设备驱动程序、系统调用处理程序等等。宏内核的优势是效率高，因为微内核不同层次之间的消息传递等需要花费一定的代价。Linux内核提供了模块，其代码可以在运行时链接到内核或从内核解除链接。

Unix文件系统概述

Unix文件是以字节序列组成的信息载体，内核不解释文件的内容。从用户的观点来看，文件被组织在一个数结构的命名空间中。树的根对应的目录被称为根目录。Unix的每个进程都由一个当前工作目录，它属于进程执行上下文，标识出进程所用的当前目录。

• 绝对路径： 路径名的第一个字符是‘/’
• 相对路径： 路径名的第一个字符不是‘/’

硬连接指通过索引节点来进行连接。硬连接的作用是允许一个文件拥有多个有效路径名，这样用户就可以建立硬连接到重要文件，以防止“误删”的功能。硬链接有两方面的限制：

• 不允许用户给目录创建硬链接。避免出现环形目录结构体
• 只有在统一文件系统中的文件之间才能创建硬链接。

软链接也称符号连接symbolic link。软链接文件有类似于Windows的快捷方式。它实际上是一个特殊的文件。在符号连接中，文件实际上是一个文本文件，其中包含的有另一文件的位置信息，可以是位于任意一个文件系统的任意文件或目录。

文件可以是下列类型之一：

• 普通文件 regular file
• 目录
• 符号链接
• 面向块的设备文件 block-oriented device file
• 面向字符的设备文件 character-oriented device file
• 管道pipe和命名管道named pipe，也教FIFO
• 套接字 socket

文件系统处理文件需要的所有信息包含在一个名为索引节点inode的数据结构体中。每个文件都有自己的索引节点，文件系统用索引节点来标识文件。索引节点至少提供如下信息：

• 文件类型
• 与文件相关的硬链接个数
• 以字节为单位的文件长度
• 设备标识符，即包含文件的设备的标识符
• 在文件系统中标识文件的索引节点号
• 文件拥有者的UID
• 文件的用户组ID
• 几个时间戳，表示索引节点状态改变的时间、最后访问时间及最后修改时间
• 访问权限和文件模式

访问权限和文件模式
文件的潜在用户分为三种类型：

• 作为文件所有者的用户
• 同组用户，不包括所有者
• 所有剩下的用户

文件的访问权限也有三种：

• 读
• 写
• 执行

因此，文件访问权限的组合就用9种不同的二进制来标记。
还有三种附加的标记，即suid Set User ID、sgid Set Group ID及sticky用来定义文件的模式。

• suid。 进程执行一个文件时通常保持进程拥有者的UID。然而，如果设置了可执行文件suid的标志位，进程就获得了该文件拥有者的UID。
• sgid。 进程执行一个文件时通常保持进程组的用户组ID。然而，如果设置了可执行文件sgid的标志位，进程就获得了该文件用户组的ID。
• sticky。设置了sticky标志位的可执行文件相当于向内核发出一个请求，当程序执行结束以后，依然将它保留在内存。该标志已经过时。

当文件由一个进程创建时，文件拥有者的ID就是该进程的UID。而其用户组ID可以是进程创建者的ID，也可以是父目录的ID，这取决于父目录sgid标志位的值。

文件操作的系统调用

• 打开文件。进程只能访问打开的文件。
• 访问打开的文件。可以顺序/随机地访问。对设备文件和命名管道文件，通常只能顺序访问。
• 关闭文件。释放与文件描述符fd相对应的打开文件对象。当一个进程终止时，内核会关闭其所有仍然打开着的文件。
• 更名及删除文件。不需要打开就可以更名和删除文件。实际上，该操作并没有对这个文件的内容起作用，而是对一个或多个目录的内容起作用。

Unix内核概述

内核本身并不是一个进程，而是进程的管理者。进程/内核模式假定：请求内核服务的进程使用所谓的系统调用system call的特殊编程机制。每个系统调用都设置了一组识别进程请求的参数，然后执行与硬件相关的CPU指令完成从用户态到内核态的转换。

Unix系统还包括所谓内核线程kernel thread的特权进程，具有如下特点：

• 以内核态运行在内核地址空间。
• 不与用户直接交互，因此不需要终端设备。
• 通常在系统启动时创建，然后一直处于活跃状态直到系统关闭。

有几种方式激活内核例程：

• 进程调用系统调用
• 正在执行进程的CPU发出一个异常信号
• 外围设备向CPU发出一个中断信号以通知一个事件的发生
• 内核线程被执行

为了让内核管理进程，每个进程由一个进程描述符process descriptor表示，这个描述符包含有关进程当前状态的信息。

当内核暂停一个进程的执行时，就把几个相关处理器寄存器的内容保存在进程描述符中。这些寄存器包括：

• 程序计数器PC和栈指针SP寄存器
• 通用寄存器
• 浮点寄存器
• 包含CPU状态信息的处理器控制寄存器，处理器状态字 processor status word
• 用来跟踪进程对RAM访问的内存管理寄存器

所有的Linux内核都是可重入的，这意味着若干个进程可以同时在内核态执行，可以包含非可重入函数，利用锁机制保证一次只有一个进程执行非重入函数。

每个进程运作在自身私有地址空间。用户态下运行的进程涉及到私有栈、数据区和代码区。在内核态运行时，进程访问内核的数据区和代码区，但使用另外的私有栈。Linux支持mmap系统调用，该系统调用允许存放在块设备上的文件或信息的一部分映射到进程的部分地址空间。

一般来说，对于全局变量的安全访问通过原子操作来保证。临界区是这样的一段代码，进入这段代码的进程必须完成，之后另一个进程才能进入。

• 非抢占式内核：当进程在内核态执行时，不能被任意挂起，也不能被另一个进程代替。
• 禁止中断。在进入一个临界区之前禁止所有的硬件中断，离开时再重新启用中断。
• 信号量。可以把信号量看成一个对象，其组成如下: 一个整数变量；一个等待进程的链表；两个原子方法down和up。
  • 当内核希望访问这个数据结构时，在相应的信号量上执行down方法。如果信号量的当前值不是负数，则允许访问这个数据结构。
  • 否则，把执行内核控制路径的进程加入到这个信号量的链表并阻塞该进程。
  • 当另一个进程在那个信号量上执行up方法时，允许信号量链表上的一个进程继续执行。
• 自旋锁。当一个进程发现锁被另一进程锁着时，不停地旋转，直到锁打开。在单处理器下自旋锁是无效的。
• 避免死锁。Linux通过按规定的顺序请求信号量来避免死锁deadlock。

Unix信号signal提供了把系统事件报告给进程的一种机制。每种事件都由自己的信号编号，通常用一个符号常量来表示，例如SIGTERM。有两种系统事件：

• 异步通告。
• 同步错误或异常。

用户态下进程间通信机制很多，通常有：信号量、消息队列及共享内存。共享内存为进程之间交换和共享数据提供了最快的方式。

进程管理：fork系统调用用来创建一个新进程；exit系统调用用来终止一个进程；exec系统调用用来装入一个新程序。

僵死进程：wait4系统调用允许进程等待，直到其中的一个子进程结束，它返回已终止子进程的进程标识符。僵死进程表示进程已经终止，父进程还没有执行完wait4。

进程组和登陆会话：现代Unix操作系统引入了进程组process group的概念，以表示一种作业job的抽象。现代Unix内核也引入了登陆会话login session。

虚拟内存：Virtual memory作为一个逻辑层，处于应用程序的内核请求与硬件内存管理单元MMU memory management unit之间。现代CPU包含了能自动把虚拟地址转换成物理地址的硬件电路。它有很多用途和优点：

• 若干个进程可以并发地执行
• 应用程序所需内存大于可用物理内存时也可以运行
• 程序只有部分代码装入内存时进程可以执行它
• 运行每个进程访问可用物理内存的子集
• 进程可以共享库函数或程序的一个单独内存映像
• 程序是可重定位的，也就是说，可以把程序放在物理内存的任何地方
• 程序员可编写与机器无关的代码
• 进程虚拟地址空间处理

进程的虚拟地址空间包括了进程可以引用的所有虚拟内存地址。通常包括如下几个内存区：

• 程序的可执行代码
• 程序的初始化数据
• 程序的未初始化数据
• 初始程序栈
• 所需共享库的可执行代码和数据
• 堆

所有现代Linux都采用了请求调页的分配策略，进程可以在它的页还没有在内存的时候就开始执行，当进程访问一个不存在的页时，MMU产生一个异常，异常处理程序分配一个空闲的页。

高速缓存：物理内存的一大优势就是用作磁盘和其他块设备的高速缓存。sync()把所有“脏”的缓冲区写入磁盘来强制同步。

设备驱动程序：内核通过设备驱动程序device driver与I/O设备交互。

内存寻址

内存地址

当使用80x86微处理器时，我们必须区分以下三种不同的地址：

• 逻辑地址：包含在机器语言指令中用来指定一个操作数或一条指令的地址。每一个逻辑地址都由一个段和一个偏移量组成。
• 线性地址/虚拟地址：是一个32位无符号整数，可用来表达4GB地址。
• 物理地址：用于内存芯片级内存单元寻址。

内存控制单元（MMU）通过一种称为分段单元的硬件电路把逻辑地址转换成线性地址，第二个称为分页单元的硬件电路把线性地址转换为物理地址。

硬件中的分段

段选择符和段寄存器

一个逻辑地址由两部分组成：段标识符（16位长）和指定段内相对地址的偏移量（32位长）。段寄存器的唯一目的是存放段选择符，这些段寄存器称为cs，ss，ds，es，fs和gs：

• cs：代码段寄存器，指向包含程序指令的段，有一个两位的字段用于指明当前CPU特权级。
• ss：栈段寄存器：指向包含当前程序栈的段
• ds：数据段寄存器，指向包含静态数据或全局数据段

段描述符

每个段由一个8字节的段描述符表示，它描述了段的特征。段描述符放在全局描述符表GDT或者局部描述符表LDT，GDT在主存中的地址和大小存放在gdtr控制寄存器中，而LDT的地址和大小放在ldtr中。

有几种不同的段:

• 代码段描述符表示这个段代表一个代码段
• 数据段描述符，表示这个段代表一个数据段
• 任务状态段描述符TSSD，表示这个段代表一个任务状态段TSS，只能出现在GDT中。

快速访问段描述符

一种附加的非编程寄存器含有8个字节的段描述符，每当一个段选择符被装入段寄存器，相应的段描述符就由内存装入对应的非编程寄存器。这样处理器只需要引用存放段描述符的CPU寄存器即可。

段选择符包含：

• index：指定放在GDT或LDT中的相应描述符的入口
• TI：指明段描述符是在GDT还是LDT
• RPL：请求者特权

段描述符在GDT或LDT中的相对地址是由段选择符的最高13位乘以8得到的。

分段单元

逻辑地址转换为线性地址:

• 检查段选择符的TI字段，以决定段描述符保存在哪一个描述符表中，分段单元从gdtr或者ldtr中得到线性地址。
• 从段选择符的index中得到段描述符的地址，index字段的值乘以8，结果与gdtr或ldtr寄存器中的内容相加。
• 把逻辑地址的偏移量与段描述符Base字段的值相加得到线性地址。

Linux中的分段

运行在用户态的所有Linux进程都使用一对相同的段来对指令和数据寻址。这两个段就是用户代码段和用户数据段，对内核亦然。

相应的段选择符由宏__USER_CS，__USER_DS，__KERNEL_CS，__KERNEL_DS定义。所有段都是从0x00000000开始，在Linux下逻辑地址与线性地址是一致的，即逻辑地址的偏移量字段的值与相应的线性地址的值总是一致的。

Linux GDT

所有的GDT都放在cpu_gdt_table中，而所有的GDT的地址和它们的大小被放在cpu_gdt_descr数组中。每个GDT包含18个段描述符和14个空的，使经常一起访问的段描述符能够处于同一个32字节的硬件高速缓存行中，其中：

• 用户和内核各有一个代码段和数据段
• 一个TSS任务段来保存寄存器的状态
• 包含缺省局部描述符表的段
• 3个局部线程存储
• 与高级电源管理相关的三个段
• 与支持即插即用的BIOS相关的5个段
• 被内核用来处理双重错误异常的TSS段

Linux LDT

Linux系统中，大多数用户态的程序都不使用LDT。内核定义了一个缺省的LDT共大多数进程使用。

硬件中的分页

分页单元把线性地址转换成物理地址，其中一个关键任务是把所请求的访问类型与线性地址的访问权限比较，如果访问无效则产生缺页异常。线性地址被分为固定长度为单位的组，称为页。分页单元把所有的RAM分成固定长度的页框，每一个页框包含一个页。页只是一个数据库，可以放在任何页框或者磁盘中。线性地址映射到物理地址的数据结构称为页表，通过设置cr0寄存器的PG标志启动分页，PG=0时，线性地址被解释成物理地址。

常规分页

32位线性地址被分为3个域：目录10位，页表10位，偏移量12位。转换分为两步，每一步都基于一种转换表，第一种为页目录表，第二为页表，这样可以减少每个进程页表所需的RAM数。每个活动进程必须有一个分配给它的页目录，在进程实际需要一个页表的时候才给进程分配RAM会更有效率。

页目录物理地址放在控制寄存器cr3中，每一页有4096字节的数据。线性地址内地Directory字段决定页目录中的目录项，目录项指向适当的页表，table字段决定页表中的表项，表项中含有页所在页框的物理地址，offset字段决定页框内的相对位置。

页目录项和页表项有相同的结构：

• Present标志：
  • 置1，所指页或页表在主存中；为0，不在主存中。如果当访问一个地址时，页目录项或页表项的Present标志为0，则分页单元将该线性地址存放在寄存器cr2中，产生14号异常：缺页异常。
• 包含页框物理地址最高20位的字段
• accessed
  • 每当分页单元对相应页框进行寻址时，设置这个标志。分页单元从来不重置这个标志，而是必须由操作系统去做。
• Dirty
  • 只应用于页表项中，每当对一个页框写操作时就设置。分页单元从来不重置这个标志，而是必须由操作系统去做。
• Read/Write
  • 页或页表的存取权限。与段的3种存取权限（读、写、执行）不同的是，页的存取权限只有两种（读、写）。
• User/Supervisor
  • 访问页或页表所需的特权级。若此标志为0，只有当CPL小于3（Linux：CPU处于内核态）时才能对页寻址，否则总能对页寻址。
• PCD/PWT
  • 控制硬件高速缓存处理页或页表的方式。
• Page Size
  • 只应用于页目录项。设置为1，则页目录项指向2M或4M的内存。
• Global
  • 只应用于页表项，用于防止常用页（全局页）从TLB中刷新出去。（当cr4寄存器的PGE（页全局启用）标志置位时，这个标志才有效）。

扩展分页

设置页框大小为4MB而不是4KB，允许把大段连续的线性地址转换成相应的物理地址，不需要中间页表进行转换，32位线性地址分为两个字段：10位directory和22位offset。通过设置cr4处理器寄存器的PSE标志能使扩展分页与常规分页共存。

硬件保护方案

与页和页表相关的特权级只有两个，因为特权由前面常规分页一节中所提到的User/Ssupervisor标志所控制。若这个标志为0，只有当CPL小于3时才能对页寻址；若该标志为1，则总能对页寻址。页的存取只有两种(读/写)，Read/Write为0只读，否则可读写。

物理地址扩展分页机制

从PentiumPro开始。Intel所有处理器现在寻址能力达64GB。不过，只有引入一种的分页机制把32位线性地址转换到36位物理地址才能使用所增加的物理地址。Intel引入一种叫做物理地址扩展PAE的机制。通过设置cr4控制寄存器中的物理地址扩展标志激活PAE。页目录中的页大小标志PS启用大尺寸页。

Intel为了支持PAE已经改变了分页机制：

• 64GB的RAM被分为了2的24次方个页框，页表项的物理地址字段从20位扩展到24位。因为PAE页表项必须包含12个标志位和24个物理地址。总数之和为36。页表项大小从32位变成64增加了一倍。结果，一个4KB的页表包含512个表页不是1024个表项。
• 引入一个叫做页目录指针表PDPT的页表新级别，它由4个64位表项组成。
• cr3控制寄存器包含一个27位的页目录指针表基地址字段。因为PDPT存放在RAM的前4GB中，并在32字节的倍数上对齐，因此27位足以表示这种表的基地址。
• 当把线性地址映射到4KB的页时，32位线性地址按下列方式解释：
  • cr3：指向一个PDPT
  • 位31-30：指向PDPT中4个项中的一个
  • 位29-21：指向嶡目录中512个项中的一个
  • 位20-12：指向页表中512项中一个
  • 位11-0：4KB页中的偏移量
• 当把线性地址映射到2MB的页时，32位线性地址按下列方式解释：
  • cr3：指向一个PDPT
  • 位31-30：指向PDPT中4个项中的一个
  • 位29-21：指向页目录中512个项中的一个
  • 位20-0：4KB页中的偏移量

硬件高速缓存

为了缩小CPU和RAM之间的速度不匹配，基于著名的局部性原理引入了硬件高速缓存内存。高速缓存再被细分为行的子集。

• 在一种极端的情况下，高速缓存可以是直接映射的，这时主存中的一个行总是存放在高速缓存中完全相同的位置。
• 在另一种极端情况下，高速缓存是充分关联的，这意味着主存中的任意一个行可以存放在高速缓存中的任意位置。
• 大多数高速缓存在某种程序上是N路相关联的，意味着主存中的任意一个行可以存放在高速缓存N行中的任意一行中。

高速缓存单元插在分页单元和主内存之间，包含一个硬件高速缓存内存用来存放内存中真正的行和一个高速缓存控制器用来存放一个表项数组，对应内存中的行。每个表项有一个标签tag和几个标志flag。

当命中一个高速缓存时：

• 对于读操作，控制器从高速缓存行中选择数据并送到CPU寄存器，不需要访问RAM因而节约了CPU时间。
• 对于写操作，控制器可能采用以下两个基本筻略之一，分别称之为通写和回写。
  • 在通写中，控制器总是既写RAM也写高速缓存行，为了提高写操作的效率关闭高速缓存。
  • 回写方式只更新高速缓存行，不改变RAM的内容，提供了更快的功效，当然，回写结束以后，RAM最终须被更新。
  • 只有当CPU执行一条要求刷新高速缓存表项的指令时，或者当一个FLUSH硬件信号产生时，高速缓存控制器才把高速缓存行写回到RAM中。

当高速缓存没有命中时，高速缓存行被写回到内存中，如果有必要的话，把正确的行从RAM中取出放到高速缓存的表项中。

每个CPU都有自己的本地硬件高速缓存，只要一个CPU修改了它的硬件高速缓存，它就必须检查同样的数据是否包含在其他的硬件高速缓存中，这种叫做高速缓存侦听。处理器的cr0寄存器的CD位用来启用或禁用高速缓存电路。

转换后援缓冲器TLB

80x86处理器包含了一个称为转换后援缓冲器的高速缓存用于加快线性地址的转换。当一个线性地址第一次使用时，通过慢速访问RAM中的页表计算出相应的物理地址。同时，物理地址被存放在一个TLB表项中，以便以后对同一个线性地址的引用可以快速转换。当CPU中的cr3寄存器被修改时，硬件自动使本地的TLB所有项都无效。

Linux中的分页

两级页表对32位系统来说已经足够了，但64位系统需要更多数量的分页级别。Linux采用了一种同时适用于32位和64位系统的普通分页模型。4种页表分别被为：

• 页全局目录
• 页上级目录
• 页中间目录
• 页表

对于没有启用物理地址扩展的32位系统。两级页表已经足够了。Linux通过使“页上级目录”位和“页中间目录”位全为0，从根本上取消了页上级目录和页中间目录字段。内核为页上级目录和同中间目录保留一个位置，这是通过把它们的页目录数设置为1，并把这两个目录项映射到页全局目录的一个适当的目录项而实现的。

启用了物理地址扩展的32位系统使用了三级页表。Linux的页全局目录对应80x86的页目录指针，取消了页上级目录，页中间目录对应80x86的页目录，Linux的页对应80x86的页表。最后，64位系统使用三级还是四级分页取决于硬件对线性地址的位的划分。

Linux的进程处理很大程序上依赖于分页。事实上，线性地址到物理地址的自动转换使下面的设计目录就得可行：

• 给每一个进程分配一块不同的物理地址空间，这确保了可以有效地防止寻址错误。
• 区别页和页框之不同。这就允许放在某个页框中的一个页，然后保存到磁盘上，以后重新装入这同一页时又可以被装在不同的页框中。这就是虚拟内存机制的基本要素。

线性地址字段

下列宏简化了页表处理：

• PAGE_SHIFT：指定Offset字段的位数；当用于80x86处理时，它产生的值为12。由于页内所有地址都必须能放到Offset字段中。因此80x86系统的页的大小是4096个字节。PAGE_SHIFT的值为12，可以看作以2为底的页大小的对数。这个宏由PAGE_SIZE使用以返回页的大小。最后，PAGE_MASK宏产生的值为0xfffff000，用以屏蔽offset字段的所有位。
• PMD_SHIFT：指定线性地址的Offset字段和Table字段的总位数。PMD_SIZE宏用于计算页中间目录的一个单独表项所映射的区域大小，也就是一个页表的大小。PMD_MASK宏用于屏蔽OFFSET字段与TABLE字段的所有位。
  • 大型页不使用最后一级页表，所以产生大型尺寸的LARGE_PAGE_SIZE宏等于PMD_SIZE，而在大型页地址中用于屏蔽Offset字段和Table字段的所有位的LARGE_PAGE_MASK宏，就等于PMD_MASK。
• PUD_SHIFT：指定页上级目录项能映射的区域大小的对数。PUD_SIZE宏用于计算页全局目录中的一个单独项所能映射的区域大小。PUD_MASK宏用于屏蔽Offset字段、Table字段。MiddleAir字段等。
• PGDIR_SHIFT：确定页全局目录能映射的区域大小的对象。PGDIR_SIZE宏用于计算页全局目录中一个单独表项能映射区域的大小。PGDIR_MASK宏用于屏蔽Offset，Table，等一些字段。
• PTRS_PER_PTE，PTRS_PER_PMD，PTRS_PER_PUD及PTRS_PER_PGD：用于计算页表，页中间目录，页上级目录和页全局目录表中表项的个数。当PAE被禁止时，它们产生的值为别为1024，1，1和1024。当PAE被激活时，产生的值分别为512，512，1和4。

页表处理

pte_t、pmd_t、pud_t和pgd_t分别描述页表项、页中间目录项、页上级目录和页全局目录项的格式。当PAE被激活时它们都是64位的数据类型。否则都是32位数据类型，它表示与一个单独表项相关的保护标志。五个类型转换宏(__pte,__pmd,__pud,__pgd和__pgprot)把一个无符号整数转换成所需要类型。另外的五个类型转换宏(pte_val,pmd_val,pud_val,pgd_val和pgprot_val)执行相反的转换，即把上面提到的四种特殊的类型转换成一个无符号整数。

内核还提供了许多宏和函数用于读或修改页表表项：

• 如果相应的表项值为0，那么，宏pte_none,pmd_none,pud_none和pgd_none产生的值为1，否则产生的值为0。
• 宏pte_clear,pmd_clear,pud_clear和pgd_clear清除相应页表的一个表项，由此禁止进程使用由该页表项映射的线性地址。
• ptep_get_and_clear()函数清除一个页表项并返回前一个值。
• set_pte,set_pmd,set_pud和set_pgd向一个页表项中写入指定的值。set_pte_atomic与set_pte的作用相同，但是当PAE被激活时它同样能保证64位的值被原子地写入。
• 如果A和B两个页表项指向同一个页并且指定相同的访问优先级，那么pte_same(A,B)返回1，否则返回0。
• 如果页中间目录项e指向一个大型页，那么pmd_large返回1，否则返回0。
• 宏pmd_bad由函数使用并通过输入参数传递来检查页中间目录项。如果目录项指向一个不能使用的页表，则这宏产生的值为1；
  • 页不在主存中
  • 页只允许读访问
  • Acessed或者Dirty被清除。

如果一个页表项的Present标志或者pagesize标志等于1，则pte_present宏产生的值为1，否则为0。对于当前在主存中却又没有读、写或执行权限的页，内核将其Present和PageSize分别标记为0和1。这样，任何试图对此类页的访问都会引起一个缺页异常。因为页的present标志清0，而内核可能通过检查Pagesize的值来检测到产生异常并不是因为缺页。

如果相应表项的present标志等于1，也就是说，如果对应的页或页表被载入主存，pmd_present宏产生的值为1。pud_presetn宏和pgd_present宏产生的值总为1。

表2-5中列出的函数用来查询页表项中任意一个标志的当前值；除了pte_file()外，其它函数只有在pte_present返回1的时候。才能正常返回页表项中任意一个标志。

表2-6列出的另一组函数用于设置页表项中和标志的值。

表2-7对页表项进行操作，它们把一个页地址和一组保护标志组合成页表项，或者执行相反的操作，从一个页表项中提出页地址。

当使用两级页表时，创建或删除一个页中间目录项是不重要的。页中间目录仅含有一个指向下属页表的目录项。所以，页中间目录项只是页全局目录中的一项而已。然而当处理页表时，创建一个页表可能很复杂，因为包含页表项的那个页表可能就不存在。在这样的情况下，有必要分配一个新页框，把它填写为0，并把这个表项加入。

如果PAE被激活，内核使用三级页表。当内核创建一个新的页全局目录时，同时也分配四个相应的页中间目录；只有当父页全局目录被释放时，这四个页中间目录才以释放。

物理内存布局

在初始化阶段，内核必须建立一个物理地址映射来指定哪些物理地址范围对内核可用而哪些不可用。保留页框的页绝不能被动态分配或交换到磁盘上，内核将下列页框记为保留：

• 在不可用的物理地址范围内的页框
• 含有内核代码和已初始化的数据结构的页框

一般来说，Linux内核安装在RAM中物理地址0x00100000开始地方，也就是说，从第二个MB开始。所需页框总数依赖于内核的配置方案：典型的配置所得到的内核可以被安装在小于3M的RAM中。

• 页框0由BIOS使用，存放加电自检期间检查到的系统硬件配置。
• 物理地址从0x000a0000到0x000fffff的范围通常留给BIOS例程，并且映射ISA图形卡上的内部内存。这个区域就是所有IMB兼容PC上从640KB到1MB之间著名的洞
• 第一个MB内的其它页框可能由特定计算机模型保留。

启动时的一些步骤：

• 在启动过程的早期阶段，内核询问BIOS并了解物理内存的大小。
• 随后，内核执行machine_specific_memory_setup()函数，该函数建立物理地址映射(见表2-9)。从0x07ff0000到0x07ff2fff的物理地址范围中存有加电自检阶段由BIOS写入的系统硬件设备信息；
• 在初始化阶段，内核把这些信息拷贝到一个合适的内核数据结构中，然后认为这些页框是可用的。相反，从0x07ff3000到0x07ffffff的物理地址范围被映射到硬件设备的ROM芯片。从0xffff0000开始的物理地址范围标记为保留，因为它由硬件映射到BIOS的ROM芯片。注意BIOS也许不提供一些物理地址范围的信息。

• setup_memory()函数在machine_specific_memory_setup()执行后被调用：它分析物理内存区域表并初始化一些变量业描述内核的物理内存布局，这些变量如表2-10所示。

为了避免把内核装入一组不连续的页框里面，Linux更愿意跳过RAM的第一个MB。明确地说，Linux用PC体系结构未保留的页框来动态存放所分配的页。图2-13显示Linux怎样填充前3MB的RAM。

符号_text对应于物理地址0x00100000，表示内核代码第一个字节的地址。内核代码的结束位置由另外一个类似的符号_etext表示。内核数据分为两组：初始化过的数据和没有初始化的数据。初始化过的数据在_etext后开始，在_edata处结束。紧接着是未初始化的数据并以_end结束。

进程的页表

进程的线性地址空间分成两部分：

• 从0x00000000到0xbfffffff的线性地址，无论进程运行在用户态还是在内核态都可以寻址。
• 从0xc0000000到0xffffffff的线性地址，只有内核态的进程才能寻址。

当进程运行在用户态时，它产生的线性地址小于0xc0000000；当进程运行在内核态时，它执行内核代码，所产生的地址大于等于0xc0000000。但是，在一些情况下，内核为了检索或存放数据必须访问用户态线性地址空间。

宏PAGE_OFFSET产生的值为0xc0000000，这就是进程在线性地址空间中的偏移量，也是内核生存空间的开始之处。页全局目录的第一部分表项映射的线性地址小于0xc0000000,具体大小依赖于特定进程。

内核页表

内核维持着一组自己使用的页表，驻留在所谓的主内核页全局目录中。系统初始化后，这组页表还从未被任何进程或任何内核线程直接使用。内核初始化自己的页表分为两个阶段。

• 内核创建一个有限的地址空间，包括内核的代码段和数据段、初始页表和用于存放动态数据结构的共128KB大小的空间。这个最小限度的地址空间仅够内核装入RAM和对初始化的核心数据结构。
• 内核充分利用剩余的RAM并适当地建立分页表。

临时内核页表

临时页全局目录是在内核编译过程中静态地初始化的，而临时页表是由startup_32()汇编语言函数初始化的。临时页全局目录放在swapper_pg_dir变量中。临时页表在pg0变量处开始存放，紧接在内核未初始化的数据段后面。为了映射RAM前8MB的空间，需要用到两个页表。

分页第一个阶段的目录是允许在实模式下和保护模式下都能很容易地对这8MB寻址。因此，内核必须创建一个映射，把从0x00000000到0x007fffff的线性地址和从0xc0000000和0xc07fffff的线性地址映射到从0x00000000和0x007fffff的物理地址。

内核通过把swapper_pg_dir所有项都填充为0来创建期望的映射，不过，0、1、0x300和0x301这四项除外；后两项包含了从0xc0000000到0xc07fffff间的所有线性地址。0、1、0x300和0x301按以下方式初始化：

• 0项和0x300项的地址字段置为pg0的物理地址，而1项和0x301项的地址字段置为紧随pg0后的页框的物理地址。
• 把这四个项中的Present，Reand/Write和User/Supervisor标志置位。
• 把这四个项中的Accessed、Diryt、PCD、PWD和PageSize标志清0。

汇编语言函数startup_32()也启用分页单元，通过向cr3控制寄存器装入swpper_pg_dir的地址及设置cr0控制寄存器的PG标志来达到这一目的。下面是等价的代码片段：

1
2
3
4
5

movl $swapper_pg_dir-0xc0000000, %eax
movl %eax, %cr3
movl %cr0, %eax
orl $0x80000000, %eax
movl %eax, %cr0

当RAM小于896MB时的最终内核页表

由内核页表所提供的最终映射必须把从0xc0000000开始的线性地址转化为从0开始的物理地址。宏__pa用于把从PAGE_OFFSET开始的线性地址转换成相应的物理地址，而宏__va做相反的转化。主内核页全局目录仍然保存在swapper_pg_dir变量中。它由paging_init()函数初始化。该函数进行如下操作：

• 调用pagetable_init()适当地建立页表项。
• 把swapper_pg_dir的物理地址写cr3控制寄存器中。
• 如果CPU支持PAE并且如果内核编译时支持PAE，则将cr4控制寄存器的PAE标志置位。
• 调用__flush_tlb_all()使TLB的所有项无效。

pagetable_init()执行的操作既依赖于现有RAM的容量，也依赖于CPU模型。计算机有小于896MB的RAM，32位物理地址足以对所有可用RAM进行寻址，因而没有必要激活PAE机制。

我们假定CPU是支持4MB页和“全局”TLB表项的最新80x86微处理器。注意如果页全局目录项对应的是0xc0000000之上的线性地址，则把所有这些项的User/Supervisor标志清0。由此拒绝用户态进程访问内核地址空间。还要注意PageSize被置位使得内核可能通过使用大型而对RAM进行寻址。

由startup_32()函数创建的物理内存前8MB的恒等映射用来完成内核的初始化阶段。当这种映射不再必要，内核调用zap_low_mappings()函数清除对应的页表项。

当RAM大小在896MB和4096MB之间时的最终内核页表

在这种情况下，并不把RAM全部映射到内核地址空间。Linux在初始化阶段可以做的最好的事是把一个具有896MB的RAM窗口映射到内核线性空间。如果一个程序需要对现在RAM的其余部分寻址，就必须把某些其它的线性地址间隔映射到所需的RAM。这意味着修改一些页表的值。

当RAM大于4096MB时的最终内核页表

如果RAM大于4GB计算机的内核页表初始化；更确切地说，要处理以下发生的情况：

• CPU模型支持物理地址扩展
• RAM容量大于4GB
• 内核以PAE支持来编译

尽管PAE处理36位物理地址，但是线性地址依然是32位地址，如前所述，Linux映射一个896MB的RAM窗口到内核线性地址空间，剩余RAM留着不映射，并由动态重映射来处理。主要差异是使用三级分页模型，因此页全局目录按以下循环代码初始化：

而全局目录中的前三项与用户线性地址空间相对应，内核用一个空页的地址对这三项进行初始化。第四项用页中间目录中的前448项用RAM前896MB的物理地址填充。

注意，支持PAE的所有CPU模型也支持大型2MB页和全局页。正如前一种情况一样，只要可能，Linux使用大型页来减少页表数。

然后页全局目录的第四项被拷贝到第一项中，这样好为线性地址空间的前896MB中的低物理内存映射做镜像。为了完成对SMP系统的初始化，这个映射是必需的：当这个映射不再必要时，内核通过调用zap_low_mapping()函数来清除对应的页表项。

固定映射的线性地址

我们看到内核线性地址第四个GB的初始部分映射系统的物理内存。但是，至少128M的线性地址总是留作他用，因为内核使用这些线性地址实现非连续内存分配和固定映射的线性地址。非连续内存分配仅仅是动态分配和释放内存页的一种特殊方式。

固定映射的线性地址基本上是一种类似于0xffffc000这样的常量线性地址，其对应的物理地址不必等于线性地址减去0xc0000000，而是可以以任意方式建立。因此，每个固定映射的线性地址都映射一个物理内存的页框。其实主是使用固定映射的线性地址来代替指针变量，因为这些变量的值从不改变。

就指针变量而言，固定映射的线性地址更有效。事实上间接引用一个立即常量地址要多一次内存访问。此外，在间接引用一个指针变量之前对其值进行检查是一个良好的编程习惯。

每个固定映射的线性地址都定义于enum fixed_address数据结构中的整型索引来表示。每个固定映射的线性地址都存放在线性地址第四个GB的低端。fix_to_virt()函数计算从给定索引开始的常量线性地址：

1
2
3
4
5

inline unsigned long fix_to_virt(const unsigned int idx) {
    if (idx >= __end_of_fixed_addresses)
        __this_fixmap_does_not_exist();
    return (0xfffff000UL - (idx << PAGE_SHIFT));
}

假定某个内核函数调用fix_to_virt(FIX_IO_APIC_BASE_0)。FIX_IO_APIC_BASE_0是个等于3的常量，因此编译程序可以去掉if语句，因为它的条件在编译时为假。相反，如果条件为真，或者fix_to_virt()参数不是一个常量，则编译程序在连接阶段产生一个错误，因为__this_fixmap_does_not_exist没有定义。

为了把一个物理地址与固定映射的线性地址关联起来，内核使用set_fixma(idx,phys)和set_fixmap_nocache(idx,phys)宏。这两个函数都把fix_to_virt(idx)线性地址对应一个页表项初始化为物理地址phys；不过，第二个函数也把页表项的PCD标志置位，因此，当访问这个页框中的数据时禁用硬件高速缓存。反过来，clear_fixmap(idx)用来撤销固定映射线性地址idx和物理地址之间的连接。

处理硬件高速缓存和TLB

采用一些技术来减少高速缓存和TLB的未命中次数。

处理硬件高速缓存

L1_CACHE_BYTES宏产生以字节为单位的高速缓存行的大小。为了使高速缓存的命中率达到最优化，内核在下列决策中考虑体系结构：

• 一个数据结构中最常使用的字段放在该数据结构内的低偏移部分，以便它们能够处于高速缓存的同一行中。
• 当为一大组数据结构分配空间时，内核试图把它们都存放在内存中，以便所有高速缓存行按同一方式使用。

处理TLB

处理器不能自动同步它们自己的TLB高速缓存，因为决定线性地址和物理地址之间映射何时不再有效的是内核，而不是硬件。Linux2.6提供了几种在合适时机应当运用的TLB刷新方法，这取决于页表更换的类型。

Intel微处理器只提供了两种使TLB无效的技术：

• 在向cr3寄存器写入值时所有Pentium处理器自动刷新相对于非全局页的TLB表项。
• 在pentiumPro及以后的处理器中，invlpg汇编语言指令使映射指定线性地址的单个TLB表项无效。

表2-12列出了采用这种硬件技术的Linux宏；这些宏是实现独立于系统的方法的基本要点。

一般来说，任何进程切换都会暗示着更换活动页表集。相对于过期页表，本地TLB表项必须被刷新：这个过程在内核把新页全局目录的地址写入cr3控制寄存器时会自动完成。不过内核在下列情况下将避免TLB被刷新：

• 当两个使用相同页表集的普通进程之间执行进程切换时。
• 当在一个普通进程一个内核线程执行进程切换时。事实上，内核线程并不拥有自己的页表集；更确切地说，它们使用刚在CPU上执行过的普通进程的页表集。

为了避免多处理器系统上无用的TLB刷新，内核使用一种叫做懒惰TLB模式的技术。其基本思想是，如果几个CPU正在使用相同的页表，而且必须对这些CPU上的一个TLB表项刷新，那么，在一些情况下，正在运行内核线程的那些CPU上的刷新就可以廷迟。处于懒惰TLB模式的每个CPU都不刷新相应的表项；但是，CPU记住它的当前进程正运行在一组页表上，而这组页表的TLB表项对用户态地址是无效的。只要处于懒惰TLB模式的CPU用一个不同的页表集切换到一个普通进程，硬件就自动刷新TLB表项，同时内核把CPU设置为非懒惰TLB模式。