《Linux内核设计与实现》

---

前言

---

第1章：Linux内核简介

通常，一个内核由负责响应中断的中断服务程序，负责管理多个进程从而分享处理器时间的调度程序，负责管理进程地址空间的内存管理程序和网络、进程间通信等系统服务程序共同组成。

在系统中运行的应用程序通过系统调用与内核通信。当一个应用程序执行一条系统调用时，应用程序被称为通过系统调用在系统空间运行，而内核被称为运行于进程上下文中。

许多操作系统的中断服务程序，包括Linux的，都不在进程上下文中执行。它们在一个与所有进程都无关的、专门的中断上下文中运行。之所以存在这样一个专门的执行环境，就是为了保证中断服务程序能够在第一时间响应和处理中断请教，然后快速地退出。

第3章：进程管理

进程

每个线程都拥有一个独立的程序计数器、进程栈和一组进程寄存器。内核调度的对象是线程，而不是进程。
fork()系统调用从内核返回两次：一次回到父进程，另一次回到新产生的子进程。

进程描述符及任务结构

内核把进程的列表存放在叫做任务队列的双向循环链表中。
链表中的每一项都是类型为task_struct，称为进程描述符的结构

分配进程描述符

Linux通过slab分配器分配task_struct结构。各个进程的task_struct存放在它们内核栈的尾部，这样可以直接通过栈指针计算出它的位置，而避免使用额外的寄存器专门记录

进程描述符的存放

pid的最大值默认设置为32768
访问任务需要获得指向其task_info指针，通过current宏可以查看正在运行进程的进程描述符

   #define current get_current()
   #define get_current() (current_thread_info()->task)
   可以看出，current调用了 current_thread_info函数，此函数的内核路径为： arch/arm/include/asm/thread_info.h，内核版本为2.6.32.65
1
2
3

进程状态

state域描述描述了进程的当前的状态
注意一下两个睡眠状态：
TASK_INTERRUPTIBLE(可中断)：可中断睡眠状态的进程在睡眠状态等待某特定事件发生，即使其等待的某特定事件没有发生，可中断休眠状态的进程也是可以被唤醒的。如：用户空间等待条件变量，在条件满足之前，也是可以被信号唤醒的 。产生一个中断、释放进程正在等待的系统资源或是传递一个信号 都可以唤醒可中断休眠状态的进程。用户空间的条件变量和互斥锁、sleep函数、内核空间的互斥锁mutex_lock_interruptible和信号量down_interruptible函数等都可以导致进程进入可中断休眠状态。
TASK_UNINTERRUPTIBLE(不可中断)：不可中断睡眠状态与可中断睡眠状态类似，但是不可中断休眠的进程必须等到某特定事件发生后才能被唤醒。将信号（如：kill函数发出的信号）传递到这种睡眠状态的进程不能改变它的状态（因为发送给处于不可中断休眠状态的进程的信号会被丢弃掉），也就是说它不响应信号的唤醒或者被调试（如：gdb，pstack等）。等待IO响应（如：磁盘IO，网络IO，其他外设IO等）、内核空间的互斥锁mutex_lock函数等都可以导致进程进入不可中断休眠状态。

设置当前进程的状态

进程上下文切换

调用系统调用，进入内核态，此时我们称内核“代表进程执行”并处于进程上下文中。
系统调用和异常处理程序是对内核明确定义接口。进程只有通过这些接口才能陷入内核执行-----对内核的所有访问都必须通过这些接口。

进程家族树

所有的进程都是pid为1的init进程的后代，内核在系统启动的最后阶段启动init进程，该进程读取系统的初始化脚本并执行其他的相关程序，最终完成系统启动的整个过程。
系统中的每个进程必须有一个父进程，每个进程可以拥有0个或多个子进程。

进程创建

首先，fork()通过拷贝当前进程创建一个子进程，子进程与父进程的区别仅仅在于pid（每个进程唯一）、ppid（父进程的进程号，子进程将其设置为被拷贝进程的pid）和某些资源和系统计量（例如，挂起的信号，没有必要被继承）。exec()函数负责读取可执行文件并将其载入地址空间开始运行。

写时拷贝

内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝，只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。
fork()的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符。

fork()

fork()、vfork()和_clone()去调用clone(),clone()去调用do_fork()，do_fork()调用copy_process()。
copy_process()工作流程如下：
（1）调用dup_task_struct()为新进程创建一个内核栈，thread_info结构和task_struct，这些值与当前进程的值完全相同。此时，子进程和父进程的描述符是完全相同的
（2）检查并确保新创建这个子进程后，当前用户所拥有的进程数目没有超出给它分配的资源的限制
（3）子进程着手使自己与父进程区别开来
（4）子进程的状态被设置为TASK_UNINTERRUPTIBLE(不可中断)，以保证它不会投入运行
（5）copy_process()调用copy_flags()以更新task_struct的flags成员。表明进程是否拥有超级用户权限的PF_SUPERPRIV标志被清0。
（6）调用alloc_pid()为新进程分配一个有效的pid。
（7）根据传递给clone()的参数标志，copy_process()拷贝或共享打开的文件、文件系统信息、信号处理函数、进程地址空间和命名空间等。
（8）最后，copy_process()做扫尾工作并返回一个指向子进程的指针
再回到do_fork()函数，如果copy_process()函数成功返回，新创建的子进程被唤醒并让其投入运行。内核有意选择子进程首先执行。如果父进程首先执行的话，有可能会开始向地址空间写入。

线程在linux中的实现

线程仅仅被视为一个与其他进程共享某些资源的进程。每个线程都拥有唯一隶属于自己的task_struct，所以在内核中，它看起来就像是一个普通的进程（只是线程和其他一些进程共享某些资源，如地址空间）。

创建线程

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

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

内核线程

内核线程和普通进程间的区别在于内核线程没有独立的地址空间（实际上指向地址空间的mm指针被设置为NULL）。
内核线程只能由其他内核线程创建。

进程终结

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

删除进程描述符

在调用do_exit()后，系统仍保留了它的进程描述符，可以让系统仍有办法获得它的信息。进程终结时所需的清理工作和进程描述符的删除是被分开执行的。在父进程获得已终结的子进程的信息后，或者通知内核它并不关注那些信息后，子进程的task_struct结构才被释放。
释放进程描述符时，release_task()会被调用。

孤儿进程造成的进退维谷

解决孤儿进程的方法：给子进程在当前线程组内找一个线程作为父亲，如果不行，就让init做它们的父进程

第4章：进程调度

多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。多任务系统划分为两类：非占式多任务和抢占式多任务。
对于抢占式多任务：由调度程序决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会。这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间是预先设置好的，叫进程的时间片。时间片就是分配给每个可运行进程的处理器时间段，有效管理时间片能使调整程序从系统全局的角度做出调度决定，可以避免个别进程独占系统资源。

Linux的进程调度

策略

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

进程可被划分为I/O消耗型和处理器消耗型。
I/O消耗型：进程的大部分时间用来提交I/O请求或是等待I/O请求。此类进程经常处于运行态，但运行时间较短，它在等待更多的I/O请求时最后总会阻塞。
处理消耗型：进程把时间大多用在执行代码上，除非被抢占，否则它们通常一直在不停的运行，调度策略往往是尽量降低它们的调度频率，延长其运行时间

进程优先级

通常做法是（并未被Linux系统完全采用）优先级高的先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。调度程序总是选择时间片未用尽且优先级最高的进程运行。

Linux采用了两种不同的优先级范围：
第一种：用nice值，范围是从-20到+19，默认值为0；越大的nice，优先级越低。相比高nice值（低优先级）的进程，低nice值（高优先级）的进程可以获得更多的处理器时间。在Linux系统中，nice值代表时间片的比例。通过ps -el查看系统的进程列表，N1一列就是进程对应的nice值
第二种：实时优先级，默认情况下它的变化范围是从0到99（包括0和99）。与nice值意义相反，越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通的进程，查看进程列表，以及它们对应的实时优先级（位于RTPRIO列下），其中如果有进程对应列显示“-”，则说明它不是实时进程。

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。
Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的，这个比例进一步还会受进程nice值的影响，nice值作为权值将调整进程所使用的处理器使用比。
在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则，将推迟其运行。

调度策略的活动

Linux调度算法

调度器类

Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。
模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

Unix系统中进程的调度

公平调度

CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了。
CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值（越低的优先级）进程获得更低的处理器使用权重。
每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行，为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标，这个目标称作“目标延迟”。注意，此时如果进程数量无限多，它们各自所获得的处理器使用比和时间片都将趋于0，这样无疑造成了不可接受的切换消耗。为此CFS引入每个进程获得的时间片底线，这个底线称为最小粒度，默认情况值是1ms。
CFS称为公平调度是因为它确保给每个进程公平的处理器使用比。

Linux调度的实现

时间记账

所有的调度器都必须对进程运行时间做记账。
1.调度器实体结构
CFS为了确保每个进程只在公平分配给它的处理时间内运行，来维护每个进程运行的时间记账。

2.虚拟实时
vruntime变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算是被加权的。
对于优先级相同的所有进程的虚拟时间是相同的，所有任务都将接受到相等的处理器份额，但是实际中处理器必须依次运行每个任务，因此CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

进程选择

当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。
CFS使用 红黑树来组织可运行进程队列， 并利用其迅速找到最小vruntime值的进程。
1.挑选下一个任务
红黑树节点的键值便是可运行进程的虚拟运行时间。找所有进程中vruntime最小的那个，便是 树中最左侧的叶子节点（rbtree用来加速寻找过程）。
更容易的做法便是把最左叶子节点缓存起来，这个函数的返回值便是CFS调度选择的下一个运行进程，如果返回值为NULL，表示没有最左叶子节点，没有可运行的进程了

2.向树中加入进程

3.从树中删除进程

调度器入口

进程调度主要入口是函数schedule（）：主要工作是以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级道德调度类中，选择最高优先级的进程。
遍历每一个调度类，每一个调度类都实现了pick_next_task()函数，它会返回指向下一个可运行进程的指针，或者没有时返回NULL。从第一个返回非NULL值的类中选择下一个可运行的进程。
注意：CFS是普通进程的调度类，而系统运行的绝大多数进程都是普通进程

睡眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行状态。
内核对休眠的进程操作都相同：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule（）选择和执行一个其他进程。
**唤醒的过程刚好相反：**进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

1.等待队列
等待队列是由等待某些事件发生的进程组成的简单链表。
进程把自己放入等待队列中并设置成不可执行状态。当与等待队列相关的事件发生的时候，队列上的进程会被唤醒，为了避免产生竞争条件，休眠和唤醒的实现不能有纰漏。

2.唤醒

抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程。
每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数，完成以下工作：
（1）调用switch_mm()函数，该函数负责把虚拟内存从上一个进程映射切换到新进程中
（2）调用switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息。

为此内核是怎么知道要进行进程切换呢？
内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时，scheduler_tick()就会设置这个标志；当一个优先级更高的进程进入执行状态的时候，try_to_wake_up()也会设置这个标志；内核检查该标志确认其被设置，调用schedule()来切换到一个新的进程。该标志被设置的时候，表明有其他进程应当被运行了，要尽快调用调度程序。

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

**注意：**每个进程都包含一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量快（因为current宏速度很快并且描述符通常在高速缓存中）

用户抢占

内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。
用户抢占在一下情况是时产生：
（1）从系统返回用户空间时
（2）从中断处理程序返回用户空间时。
注意： 在返回用户空间时，都会检查need_resched标志

内核抢占

在2.6版的内核中，内核引入了抢占内力；现在，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。

什么时候重新调度是安全的？
只要没有持有锁，内核就可以进行抢占。锁是非抢占区域的标志。

内核抢占的具体过程：
每个进程的thread_info引入preempt_count计数器，初值为0。当使用锁时候数值加1，释放锁时候数值减1。当数值为0时候，内核就可执行抢占。
从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值，如果need_resched被设置，并且preempt_count为0的话，说明有一个更为重要的任务需要执行并且可以安全的抢占，此时调度程序就会被调用
如果preempt_count不为0，说明当前任务持有锁，所以抢占是不安全的，这是内核就会像通常那样直接从中断返回当前执行进程。
如果preempt_count为0，释放锁的代码就会检查need_resched是否被设置，如果是的话，就会调用调度程序。
如果内核中的进程被阻塞了，或它显示地调用schedule()，内核抢占也会显式地发生。

由此可见，内核抢占会发生在：
（1）中断处理程序正在执行，且返回内核空间之前
（2）内核代码再一次具有可抢占性的时候
（3）如果内核中的任务显示地调用schedule()
（4）如果内核中的任务阻塞（这同样也会导致调用schedule()）

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。
普通的、非实时的调度策略是SCHED_NORMAL

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

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

与调度相关的系统调用

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

第5章：系统调用

与内核通信

系统调用在用户空间进程和硬件设备之间添加了一个中间层。
该层的作用：
（1）为用户空间提供了一种硬件的抽象接口
（2）系统调用保证了系统的稳定和安全，内核可以基于权限、用户类型和其他一些规则对需要进行的访问进行裁决
（3） 在Linux中系统调用是用户空间访问内核的唯一手段，除异常和陷入外

API、POSIX和C库

如下图给出了POSIX、API、C库以及系统调用之间的关系：

系统调用

系统调用号

在Linux中，每个系统调用被赋予一个系统调用号。当用户空间的进程执行一个系统调用的时候，这个系统调用就用来指明到底是要执行哪个系统调用，进程不会提及系统调用的名称。

系统调用号一旦分配就不能再有任何变更，否则编译好的应用程序就会崩溃。并且如果一个系统调用被删除，它所占用的系统调用号也不允许被回收利用，否则以前编译过的代码会调用这个系统调用，事实上却调用的是另一个系统调用。

系统调用的性能

系统调用处理程序

用户空间的程序无法直接执行内核代码，不能直接调用内核空间中的函数，内核驻留在受保护的地址空间上

内核态进行切换的方法：
通知内核的机制是靠软中断实现的：通过引发一个异常来促使系统切换到内核态去执行异常处理程序。此时的异常处理程序实际上就是系统调用处理程序。（中断号）

指定恰当的系统调用

所有系统调用陷入内核的方式都一样，所以仅仅是陷入内核空间是不够的，还需要把系统调用号一并传给内核。

参数传递

在调用系统调用的时候，还需要传递些参数给内核。
传递这些参数也和传递系统调用号一样，也是存放在寄存器里
给用户空间的返回值也通过寄存器传递

系统调用的实现

实现系统调用

第6章：内核数据结构

链表

因为环形双向链表提供了最大的灵活性，所以Linux内核的标准链表就是采用环形双向链表形式实现的。

Linux内核中的实现

Linux内核方式与众不同，它不是将数据结构塞入链表，而是将链表节点塞入数据结构
1.链表数据结构

2.定义一个链表
链表本身没有意思，需要嵌入到自己的数据结构中才能生效
如下代码：

struct fox
{
	unsigned long tail_length;
	unsigned long weight;
	bool is_fantastic;
	struct list_head list; /*所有fox结构类型形成链表*/
};
1
2
3
4
5
6
7

3.链表头
上述fox中，每个fox节点都是无差别的，每一个都包含一个list_head指针，可以从任何一个节点起遍历链表，直到看到所有节点。
但是有时需要一个特殊指针索引到整个链表，而不从一个链表 节点触发。这个特殊的索引节点事实上就是一个常规的list_head：

static LIST_HEAD(fox_list);
1

该函数定义并初始化一个名为fox_list的链表例程，这些例程中大多数都只接受一个或者两个参数：头节点或者头节点加上一个特殊链表节点。

操作链表

内核提供了一组函数来操作链表，函数都是以内联函数形式实现的，时间复杂度都为O(1)

1.向链表中增加一个 节点

list_add(struct list_head *new,struct list_head *head);
1

2.从链表中删除一个节点
调用list_del():

list_del(struct list_head *entry)
1

该函数从链表中删除entry元素。注意，该操作并不会释放entry或释放包含entry的数据结构体所占用的内存；该函数仅仅是将entry元素从链表中移走，所以该函数被调用后，通常还需要再撤销entry的数据结构体和其中的entry项。

3.移动和合并链表节点

**节约两次提领：**如果得到了next和prev指针，可以直接调用内部链表函数，从而省下一点时间（其实就是提领指针的时间），内部函数和外部包装函数同名，仅仅在前面加了两条下划线。

遍历链表

遍历链表的复杂度是O(n)

队列

kfifo

kfifo对象维护了两个偏移量：入口偏移和出口偏移。
入口偏移是指下一次入队列时的位置，出口偏移是指下一次出队列时的位置。出口偏移总是小于等于入口偏移，否则无意义，因为那样说明要出队列的元素根本还没有入队列

映射

一个映射，也常称为关联数组，其实是一个 由唯一键组成的集合，而每个键必然关联一个特定的值。这种键到值的关联关系称为映射。

二叉树

自平衡二叉搜索树

数据结构以及选择

第7章:中断和中断处理

中断

中断使得硬件可以发出通知给处理器。中断本质上是一种特殊的电信号，中断可以随时产生
不同的设备对应的中断不同，而每个中断都通过一个唯一的数字标志

异常与中断不同，它在产生时必须要考虑与处理器时钟同步，异常也常常称为同步中断

中断处理程序

在响应一个特定中断的时候，内核会执行一个函数，该函数叫做中断处理程序或中断服务例程。
中断处理程序与其他内核函数的真正区别在于，中断处理程序是被内核调用来响应中断的，而它们运行于我们称之为中断上下文的特殊上下文中。

上半部与下半部的对比

一般把中断处理切为两个部分或两半。
中断处理程序是上半部分------接受到一个中断，它就立即开始执行，但只做有严格时限的工作，例如对接收的中断进行应答或复位硬件，这些工作都是在所有中断被禁止的情况下完成的。
能够被运行稍后完成的工作会推迟到下半部分去

注册中断处理程序

中断处理程序是管理硬件的驱动程序的组成部分
如果设备使用中断（大部分设备如此），那么相应的驱动程序就注册一个中断处理程序。

中断处理程序标志

一个中断例子

初始化硬件和注册中断处理程序的顺序必须正确，以防止中断处理程序在设备初始化完成之前就开始执行

释放中断处理程序

卸载驱动程序时，需要注销相应的中断处理程序，并释放中断线。
调用：

void free_irq(unsigned int irq,void *dev)
1

编写中断处理程序

重入和中断处理程序
Linux中的中断处理程序是无须重入的。当一个给定的中断处理程序正在执行时，相应的中断线在所有处理器上都会被屏蔽掉，以防止在同一中断线上接收另一个新的中断。通常情况下，所有其他的中断都是打开的，所以这些不同中断线上的其他中断都能被处理，但当前中断线总是被禁止的。
同一个中断处理程序绝对不会被同时调用以外处理嵌套的中断

共享的中断处理程序

第9章：内核同步介绍

临界区和竞争条件

临界区（也称为临界段）就是访问和操作共享数据的代码段
避免并发和防止竞争条件称为同步

为什么我们需要保护

单个变量

加锁

不同的锁，当锁已经被其他线程持有，不可用时的行为表现不一样；如，一些锁被被争用时会简单地执行忙等待（反复处于一个循环中，不断检测锁状态，等待锁变为可用），另外一些锁会使当前任务睡眠直到锁变为可用为止。互斥锁、自旋锁、原子操作的原理、区别及应用场景
锁是采用原子操作实现的

造成并发执行的原因

内核可能造成并发执行的原因：
（1）中断
（2）软中断和tasklet
（3）内核抢占----因为内核具有抢占性，所以内核中的任务可能会被另一任务抢占
（4）睡眠及与用户空间的同步----在内核执行的进程可能会睡眠，这就会唤醒调度程序，从而导致调度一个新的用户进程执行
（5）对称多处理-----两个或多个处理器可以同时执行代码

了解要保护些什么

死锁

死锁产生需要一定的条件：要有一个或多个执行线程和一个或多个资源，每个线程都在等待其中的一个资源，但所有的资源都已经被占用了。所有线程都在相互等待，但它们永远不会释放已经占有的资源 。于是任何线程都无法继续，这便意味着死锁的发生。
例子：
自死锁（可以用递归锁来防止）
ABBA锁

一些简单的规则对避免死锁大有帮助：
（1）按顺序加锁。使用嵌套的锁时必须保证以相同的顺序获取死锁，这样可以阻止致命拥抱类型的死锁。最好能记录下锁的顺序，以便其他人也能照此顺序使用
（2）防止发生饥饿
（3）不要重复请求一个锁
（4）设计应力求简单----越复杂的加锁方案越有可能造成死锁
如果有两个或多个锁曾在同一时间里被请求，那么以后其他函数请求它们也必须按照前次的加锁顺序进行。如下所示：
线程1：
获得锁cat
获得锁dog
试图获得锁fox
等待锁fox

线程2：
获得锁fox
试图获得锁dog
等待锁 dog
……

线程1在等待锁fox，而该锁此刻被线程2持有；同样线程2正在等待锁dog，而该锁此刻又被线程1持有。任何一方都不会放弃自己持有的锁，于是双方都会永远地等待下去--------也就是死锁。只要相同的顺序去获取这些锁，就可以避免上述的死锁情况。

只要嵌套地使用多个锁，就必须按照相同的顺序去获取它们。

争用和扩展性

锁的争用是指当锁正在被占用时，有其他线程试图获得该锁。
一个 锁处于高度争用状态，就是指有多个其他线程在等待获得该锁。
扩展性是对系统可扩展程度的一个量度
加锁粒度用来描述加锁保护的数据规模

对加锁的优化：

当锁争用严重时，加锁太粗会降低可扩展性；而锁争用不明显，加锁过细会加大系统的开销，都会造成系统性能的下降。

第10章：内核同步方法

原子操作

原子操作可以保证指令以原子的方式执行-------执行过程不被打断

原子整数操作

原子性与顺序性的比较

原子性确保指令执行期间 不被打断，要么全部执行完，要么根本不执行 。
顺序性确保即使两条或多条指令出现在独立的执行线程中，甚至独立的处理器上，它们本该的执行顺序却依然要保持。

原子位操作

自旋锁

一个被争用的自旋锁使得请求它的线程在等待锁重新可用时自旋（特别浪费处理器时间）
自旋锁的初衷：在短时间内进行轻量级加锁。
普通的加锁，睡眠等待：有两次明显的上下文切换 ，被阻塞的线程要换出和换入。
持有自旋锁的时间最好小于完成两次上下文切换的耗时

自旋锁方法

自旋锁是不可递归的

读——写自旋锁

Linux内核提供了专门的读——写自旋锁）（共享/排斥锁），这种自旋锁为读和写分别提供了不同的锁。一个或多个读任务可以并发地持有读者锁；用于写的锁最多只能被一个写任务持有，而且此时不能有并发的读操作

信号量

Linux中的信号是一种睡眠锁。如果有一个任务试图获得一个不可用（已经被占用）的信号量时，信号量会将其推进一个等待队列，然后让其睡眠。

从 信号量的睡眠特性可以得出一些结论：
（1）由于争用信号量的进程在等待锁重新变为可用时会睡眠，所以信号量适用于锁会被长时间持有的情况
（2）锁被长时间持有时，使用信号量就不太适宜了。因为睡眠、维护等待队列以及唤醒所花费的开销可能比锁被占用的全部时间还要长。
（3）由于执行线程在锁被争用时会睡眠，所以只能在进程上下文中才能获取信号量锁。
（4）在持有信号量时去睡眠，当其他进程试图获得同一信号量时不会因此而死锁（该进程也只是去睡眠而已，而最终会继续执行的）
（5）在占用信号量的同时不能占用自旋锁。在等待信号量时可能会睡眠，而持有自旋锁时是不允许睡眠的

信号量不同于自旋锁，它不会禁止内核抢占，持有信号量的代码可以被抢占

计数信号量和二值信号量

信号量可以同时运行任意数量的锁持有者，而自旋锁在一个时刻最多允许一个任务持有它。信号量同时允许的持有者数量可以在声明信号量时指定。这个值称为使用者数量（数量）。
通常情况下，信号量和自旋锁一样，在一个时刻仅允许有一个锁持有者，这时计数等于1，这样的信号量被称为二值信号量（因为它或者由一个任务持有，或者根本没有任务持有它）或者称为互斥信号量（因为它强制进行互斥）

信号量支持两种操作down()和up()。down()操作通过对信号量减1来请求获得一个信号量。如果结果是0或大于0，获得信号量锁，任务就可以进入临界区。如果是负数，任务会被放入等待队列。降低（down）一个信号量就等于获取该信号量。up()来释放信号量 ，增加信号量的计数值，如果在该信号量上的等待队列不为空，那么处于队列中等待的任务在被唤醒的同时会获得该信号量。

读——写信号量

读——写信号量都是互斥信号量，引用计数等于1，只对写者互斥，不对读者。
读——写信号量可以动态地将获取的写锁转换为读锁。

互斥体

更简单睡眠锁。
使用规则：
（1）任何时刻中只有一个任务可以持有mutex（mutex的使用计数永远是1）
（2）在同一上下文中上锁和解锁
（3）递归地上锁和解锁是不允许的
（4）当持有一个mutex时，进程不可以退出
（5）mutex不能在中断或者下半部分中使用

完成变量

一个任务需要发出信号通知另一个任务发生了某个特定事件，利用完成变量是使两个任务得以同步的简单方法

BLK:大内核锁

BKL(大内核锁)是一个全局自旋锁

顺序锁（seq锁）

用于读写共享。实现这种 锁主要依靠一个序列计数器。
当有疑义的数据被写入时，会得到一个锁，并且序列值会增加。在读取数据之前和之后，序列号都被读取，如果读取的序列号值相同，说明在读操作进行的过程中没有被写操作打断过。如果读取的值是偶数，那么表明写操作没有发生（因为锁的初值是0，所以写锁会使值成奇数，释放的时候变成偶数）

seq锁的使用场景：
数据存在很多读者
数据写者很少
写者很少，且写优于读，不允许读者让写者饥饿
数据简单

禁止抢占

内核抢占代码使用自旋锁作为非抢占区域的标记。如果一个自旋锁被持有，内核便不能进行抢占。

顺序和屏障

数据处理时，在多处理器上，可能需要按写数据的顺序读数据（通常确保后来以同样的顺序进行读取）。
但是编译器和处理器为了提高效率，可能对读和写重新排序。
处理器提供了机器指令来确保顺序要求，同样也可以指示编译器不要对给定点周围的指令序列进行重新排序。这些确保顺序的指令称做屏障

第11章：定时器和时间管理

内核中的时间概念

硬件为内核提供了一个系统定时器用以计算流逝的时间

节拍率：HZ

系统定时器频率（节拍率）是通过静态预处理定义的，也就是HZ(赫兹)，在系统启动时按照HZ值对硬件进行设置。

理想的HZ值

系统定时器使用高频率与使用低频率有哪些优劣：
提高节拍率意外着时钟中断产生得更加频繁，中断处理程序会更频繁地执行。更高的时钟中断解析度可提高时间驱动时间的解析度；提高了时间驱动事件的准确度。

高HZ的优势

更高的时钟中断频度和更高的准确度会带来如下优点：
（1）内核定时器能够以更高的频度和更高的准确度
（2）依赖定时值执行的系统调用，比如poll（）和select（），能够以更高的精度运行
（3）对诸如资源消耗和系统运行时间等的测量会有更精细的解析度
（4）提高进程抢占的准确度
对poll（）和select（）超时精度的提高会给系统性能带来极大的好处。提高精度可以大幅度提高系统性能。频繁使用上述两种系统调用的应用程序，往往在等待时钟中断上浪费大量的时间，而事实上，定时值可能早就超时了。
更高的准确率也使进程抢占更准确，同时还会加快调度响应时间。

高HZ的劣势

jiffies

全局变量jiffies用来记录自系统启动以来产生的节拍的总数。启动时，内核将该变量初始化为0，此后，每次时钟中断处理程序就会增加该变量的值。

用户空间和HZ

硬时钟和定时器

实时时钟

实时时钟（RTC）是用来持久存放系统时间的设备

系统定时器

系统定时器提供一种周期性触发中断机制

时钟中断处理程序

时钟中断处理程序可以划分 为两个部分：体系结构 相关部分和体系结构无关部分。
与体系结构相关的例程作为系统定时器的中断处理程序而注册到内核中，以便在产生中断时，他能够相应地运行

定时器

定时器（有时也称为动态定时器或内核定时器）
定时器并不周期运行，它在超时后就自行撤销

使用定时器

内核可以保证 不会在超时时间到期前运行定时器处理函数，但是有可能延误定时器的执行。

定时器竞争条件

1.定时器与当前执行代码是异步的
2.当删除定时器时，在多处理器上定时器中断可能已经在其他处理器上运行了

实现定时器

所有定时器都以链表形式存放在一起。
为了提高搜索效率，内核将定时器按它们的超时时间划分为五组。当定时器超时时间接近时，定时器将随组一起下移。采用分组定时器的方法可以在执行软中断的多数情况下，确保内核尽可能减少搜索超时定时器所带来的负担。

延迟执行

忙等待

最简单的延迟方法是忙等待（或者说忙循环）
该方法仅仅在想要延迟的时间是节拍的整数倍，或者说精确率要求不高时才可以使用

短延迟

udelay()函数依靠执行数次循环达到延迟效果

schedule_timeout()

使用schedule_timeout()函数，该方法会让需要延迟执行的任务睡眠到指定的延迟时间耗尽后再重新运行。该方法也不能保证睡眠时间正好等于指定的延迟时间，只能尽量使睡眠时间接近指定的延迟时间。当指定的时间到期后，内核唤醒被延迟的任务并将其重新放回运行队列

第12章：内存管理

页

内核把物理页作为内存管理的基本单位
内存管理单元（MMU，管理内存并把虚拟地址转换为物理地址的硬件）通常以页为单位进行处理。
MMU以页（page）大小为单元来管理系统中的页表
系统中每个物理页都要分配一个page结构体，来管理系统中所有的页

区

内核把页划分为不同的区。
内核使用区对具有相似特性的页进行分组

Linux处理如下两种由于硬件存在缺陷而引起的内存寻址问题：
（1）一些硬件只能用某些特定的内存地址来执行DMA（直接内存访问）
（2）一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多。有一些内存不能永久映射到内核空间。

Linux使用了如下四种区：
ZONE_DMA: DMA使用的页 <16MB
ZONE_NORMAL:正常可寻址的页 16~896MB
ZONE_HIGHEM：动态映射的页 >896MB

Linux把系统的页划分为区，形成不同的内存池
如果可供分配的资源不够用了，内核就会去占用其他可用区的内存

获得页

获得填充为0的页

kmalloc（）

kmalloc()可以获得以字节为单位的一块内核内存，所分配的内存区在物理上是连续的

vmalloc（）

vmalloc（）分配的内存虚拟地址是连续的，而物理地址则无须连续
vmalloc()函数为了把物理上不连续的页转换为虚拟地址空间上连续的页，必须专门建立页表项。
通过vmalloc（）获得的页必须一个一个地进行映射（它们物理上是不连续的），会导致比直接内存映射 大得多的
TLB抖动

slab层

便于数据的频繁分配和回收，会用到空闲链表
空闲链表包含可供使用的、已经分配好的数据结构块。
当代码需要一个新的数据结构实例时，就可以从空闲链表中抓取一个，而不需要分配内存，再把数据放进去
当不再需要这个数据结构的实例时，就把它放回空闲链表，而不是释放它

slab层的设计

slab层把不同的对象划分为所谓高速缓存组，其中每个高速缓存组都存放不同类型的对象。
每种对象类型对应一个高速缓存。
slab由一个或多个物理上连续的页组成，每个高速缓存可以由多个slab组成
当内核的某一部分需要一个新的对象时，先从部分满的slab中进行分配。如果没有部分满的slab，就从空的slab中进行分配。如果没有空的slab，就要创建一个slab了。这种策略能减少碎片
高速缓存、slab及对象之间的关系：

如果slab很小，或者slab内部有足够的空间容纳slab描述符，那么描述符就存放在slab自身开始的地方，否则，另外进行分配。

在栈上的静态分配

内核栈小且固定。当给每个进程分配一个固定大小的小栈后，不但可以减少内存的消耗，而且内核也无须负担太重的栈管理任务

单页内核栈

在栈上工作

高端内存的映射

高于896MB的所有物理内存的范围大都是高端内存，它并不会永久地或自动地映射到内核地址空间

永久映射

临时映射

每个CPU的 分配

每个CPU的数据存放在一个数组中。数组中的每一项对应着系统上一个存在的处理器，按当前处理器号确定这个数组的当前元素

新的每个CPU接口

编译时的每个CPU数据