Linux内核设计与实现

第三章 进程管理

进程 是 Unix 操作系统抽象概念的最基本的一种。

进程是正在执行的程序代码的实时结果， 其不仅包含程序代码， 还包含其他的资源， 比如打开的文件， 挂起信号等， 内部数据， 处理器状态等。 因此进程是处于执行的程序以及相关资源的总称。

线程是是在进程活动的对象。 每个线程都有独立的程序计数器， 进程栈 和一组寄存器。

内核调度的对象是线程， 而不是进程。

进程提供了两种虚拟机制：虚拟处理器和虚拟内存

进程描述服以及任务结构

内核把进程存放在叫做任务队列（task list) 的双向链表中。 链表中的每一项都是类型为 task_struct， 称为进程描述符（process descriptor）的结构， 该结构定义在 <linux/sched.h>文件中。

1
2
3
4
5

struct task_struct {
    unsigned int			__state;
    struct list_head		children;  // 指向子进程
    struct task_struct __rcu	*real_parent; // 指向父进程
}

进程描述浮包含的数据能够完整的描述一个正在执行的程序：它打开的文件，进程的地址空间， 挂起信号， 进程的状态， 还有其他的跟多的信息。

分配进程描述符

Linux 通过 slab 分配器分配 task_struct

进程描述服的存放

内核通过唯一的进程标识值（process identification value） 或 PID 来标识每一个进程。 PID 是一个数， 表示为一个 pid_t 实际上是int 类型。

PID 的最大值默认设置为 32768（short int） , 你可以通过修改/proc/sys/kernel/pid_max 来提高 pid 的上限。

内核中进程相关的操作都是通过 task_struct 这个结构体进行操作， 因此必须通过一个高效的方式找到 task_struct 这个结构体。

进程的状态

进程描述的 __state 域描述了进程的状态， 系统中的每个进程必然处在下面5种进程状态一种：

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

进程的上下文

一般程序在用户空间执行。 当一个程序执行了系统调用或者触发了某个异常，它就会陷入内核空间。 此时我们称内核“代表进程执行”并处于进程的上下文中。

进程的家族树

linux 系统进程有明显的继承关系。 所有进程都是 PID 为 1 的 init 进程的后代。 内核在系统启动的最后阶段启动init 进程。 该进程会读取系统的初始化脚本并执行其他的相关程序， 最终完成系统启动的整个过程。

每个进程都有一个父进程， 有 0个或多个子进程。 进程的直接的关系都存放在进程描述中。 每个 task_strct 都有一个叫做 parent 的 task_struct 指针指向父进程， 和一个称为 children 的指针指向子进程的链表。

进程的创建

许多其他的操作系统都提供了产生（spawn）进程的机制， 首先在新的地址空间创建进程，读入可执行文件， 最后开始执行。 Linux 采用 fork（） 和 exec（）两个过程来创建进程：

• fork（） 通过拷贝当前进程创建一个子进程。 子进程和父进程的区别仅在于PID（每个进程唯一），PPID（父进程的进程号）和某些资源和统计量（例如，挂起的信号，这些没有必要被继承）。
• exec（）函数负责读取可执行文件并载入地址空间执行。

exec（） 是一族函数。 内核实现了 execve（）函数， 并再次基础上实现了 execlp（）， execle（）， execv（）和 execvp（）

写时拷贝

写时拷贝是一种延迟拷贝甚至免除拷贝的技术。 在平时页面都是以只读的方式被进程共享， 只有在写入的时候才会拷贝页面， 并在新的页面写入数据。 fork()正是利用了这个技术。

线程在 Linux 中实现

线程机制是现代编程技术中一种抽象的概念， 该机制提供了在同一个程序内共享内存地址空间运行的一组线程。 这些线程可以共享打开的文件和其它资源。

在 Linux 内核中， 线程仅被视为和其他进程共享某些资源的进程（其它专门实现线程的系统， 将线程抽象为一种耗费较少资源，运行迅速的执行单元）。 每个线程都拥有自己唯一隶属于自己的 task_struct, 所以在内核中，它看起来像一个普通的进程（只是线程和其他进程共享某些资源，如地址空间）

创建线程

创建线程和创建线程类似， 只不过在调用 clone() 的时候，传递一些参数来指名需要共享资源。

1

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

其中， 普通的 fork 实现：

1

clone(SIGCHLD, 0)

而 vfork 的实现：

1

close(CLONE_VFORK|CLONE_VM|SIGHLD, 0)

clone 参数标志

内核线程

内核通常会在后台执行一些操作。 这种任务通过内核线程完成——独立运行在内核空间的标准进程。 内核线程和普通进程区别是内核线程没有独立的地址空间（实际上指向地址空间mm 的指针设置为 NULL）.

内核线程只能由其他的内核线程创建。 内核通过从 kthreadd 内核进程中衍生处出所有的内核线程。

进程的终结

在进程终结时， 内核必须释放它所占用的资源， 并把这一不幸的消息告诉父进程。

进程的终结通常是由自身的引起的：

• 显式的调用 exit()
• 程序的主程序返回， 隐式的调用 exi（）
• 当进程接收到它既不能处理也不能忽略的信号或异常时被动终结。

删除进程描述符

在进程终结后， 进程的清理工作和进程描述符的删除被分开执行， 这样在进程终结后， 系统仍然能够获取进程的信息。

在父进程获得已经终结进程信息后，或者通知内核不关注哪些信息后， 子进程 task_struct 结构才被释放。

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

孤儿进程

如果父进程在子进程退出前， 必须保证为子进程找到找到一个父亲， 否则这些进程会成为孤儿进程在退出时就会变成僵死状态， 白白的浪费内存。

第4章 进程调度

调度程序是内核的一个子系统， 其确保进程能够高效的工作。 它能够决定那个进程投入运行，何时运行以及运行多长时间。

多任务操作系统

多任务操作系统可以分为两类：非抢占式多任务和抢占式多任务。

linux 提供了抢占多任务模式， 在此模式下， 让调度系统来决定什么时候停止一个进程的运行， 以便其他的进程得到执行的机会。 这种强制的挂起动作叫做抢占（preemption）。

进程在被抢占之前能够运行的时间都是预先设置好的， 这有个专门的名字，叫做时间片（timeslice）

相反， 在非抢占多任务模式下，除非进程主动停止运行， 否则它会一直执行。 进程主动挂起自己的操作成为让步（yielding）

Linux 调度程序

Linux的调度程序经过了：简单调度程序（2.4以前） -> O(1) 调度程序（2.6以前）-> 完全公平调度算法（现在） CFS。

策略

策略决定调度程序何时让什么进程运行。

IO消耗型和处理器消耗型的进程

IO 消耗型进程大部分时间都用来提交IO请求或等待IO请求。 这类型进程会经常处于可运行状态，但是通常都是运行短短的一会儿， 因为要等待更多的io 请求。

处理器消耗型花费大部分时间在执行代码， 除非被抢占， 否则会不停的运行。 对于处理器消耗型的调度策略往往是减少其调度频率， 增加其运行时间。

调度策略通常会在两个主要矛盾中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。

进程优先级

调度算法最基本的一类是基于优先级的调度。 这是一种根据进程的价值和其对处理器时间的需求来对进程分级的算法。 通常的做法（并未被linux 完全采用）是优先级高的进程先运行，低的后运行，相同优先级的进程按照轮转的方式进行调度（一个接一个，重复执行）。

Linux 有两种方式设置进程的优先级：

• 第一种是 nice 值， 它的范围从 -20 到+19，默认值为0； nice 值越大意味着优先级越低——nice 似乎意味着你对系统的其他进程更“优待”
• 第二种是实时优先级， 默认情况下他的变化范围从 0 到 99。 其值越大优先级越高。

时间片

时间片是一个数值， 表明进程在被抢占前所能持续运行的时间。 调度策略必须规定一个默认的时间片。 如果时间片过长， 会导致系统实时性变差。 如果时间片过短， 有会导致处理器的大部分时间消耗在进程的切换。

Linux 的 CFS 调度器并没有直接分配时间片到进程， 而是将处理器的使用比例划分给进程。 分配给进程的使的比例会受到系统的负载密切相关的，并进一步受到 nice 的值的影响， 根据nice 值调整使用比列。 nice 值更高（优先级越低）进程将被赋予更低的使用比例， nice 值更低（优先级越高）进程将被赋予更高的使用比例。

Linux 调度算法

调度器类

linux 调度是以模块的方式提供的， 这种模块称为调度器类（scheduler classes）。 每个调度器类都有一个有优先级。 我们可以动态的添加调度器模块。 最基础的调度器代码定义在 kernel/sched.c 文件中， 它会按照优先级顺序遍历调度器类， 拥有一个可以执行进程的最高优先级的调度器类胜出， 去选择下面要执行的那一个程序。

完全公平调度（CFS）是一个针对普通进程的调度器类， 在linux 中被称为SCHED_NORMAL， 并在 kernel/sched_fair.c 中定义。

公平调度

CFS 出发点基于这样一个理念：每个进程都能够获得 1/n 的处理器时间——n 是进程的数量， 并且可以调度给他们无限小的时间周期， 所以在可测量周期内， 每个进程都运行相同的时间。

Linux 调度的实现

linux 的调度相关代码位于 kernel/sched_fair.c 中 。

时间记账

所有的调度器都必须对进程的运行时间做记账。 大多数 Unix 的系统， 分配一个时间片给每一个进程， 那么当每次系统节拍发生时，时间片都会减少一个节拍周期。 当一个进程的时间片被减少到0时， 该进程会被其他未减少到0的进程抢占。

CFS调度器的结构

CFS 调度器的实体结构位于linux/sched.h 的 struct_sched_entity 中来追踪进程的时间记账。

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

struct sched_entity {
	/* For load-balancing: */
	struct load_weight		load;
	struct rb_node			run_node;
	struct list_head		group_node;
	unsigned int			on_rq;

	u64				exec_start;
	u64				sum_exec_runtime;
	u64				vruntime;
	u64				prev_sum_exec_runtime;

	u64				nr_migrations;

	struct sched_statistics		statistics;

调度器实体结构作为一个se 的成员变量，嵌入到进程描述符中。

虚拟实时

vruntime 变量存放进程的虚拟运行时间，该运行的时间（花在运行时间上的和）的计算是经过了所有可运行进程总数的标准化（或者说是加权相加的）。

CFS 采用 vruntime 来记录一个进程到底运行了多长时间以及还应该运行多长时间。

进程选择

在完美多任务处理器中，每个进程 vruntime 都一致。 而存在 CFS 中也力求进程的使用处理器的时间比公平。 在CFS 中vruntime 是对进程运行的时间进行了加权相加的， 也力求均衡进程的虚拟运行时间。 CFS 调度核心：当 CFS 会选择下一个运行的进程时，会挑选具有最小 vruntime 的进程运行。

CFS 采用红黑树来组织可运行进程队列，并利用其迅速找到最小 runtime 值的进程。 在 linux 中， 红黑树称为 rbtree，它是一个自平衡二叉搜索树。

红黑树是一种以树节点的形式存储这些数据，这些数据对应一个键值， 我们通过这些键值来快速的检索节点上的数据。（最重要的是通过键值检索到对应的即诶单的速度和节点的规模成指数比关系）。

调度器入口

在 linux 中进程调度中， 是按照模块的形式提供的。 每一个调度器算法都对应着一个调度器类， 负责进程的调度。 有一个最基本的调度器算法， 它会按照优先级， 依次遍历所有的调度器类， 并且从优先级最高的调度器类中， 选择最高优先级的进程。

进程的调度的入口函数是 schedule()， 它定义在 (kernel/sched.c) 中。

睡眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可以执行状态。 进程的休眠原因有很多种， 但肯定都是为了等待一些事件。

让一个进程变成休眠状态， 内核的操作都是相同：进程把自己标记成休眠状态， 从可执行红黑树中移除，让入等待队列， 然后调用schedule() 选择和执行下一个进程。

唤醒过程正好相反：进程被设置成可执行状态，然后再从等待队列中移到可执行队列中。

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

等待队列

休眠通过等待队列进行处理。 等待队列是由等待某些时间发生的进程组成的简单链表。

唤醒

唤醒操作通过 wake_up() 进行，它会唤醒指定队列所有上的所有进程。

抢占和上下文切换

上下文切换， 也就是从一个可执行进程切换到另外的一个可执行进程。 由定义在 kernel/sched.c 中 context_switch() 函数负责处理。

当一个新的进程准备投入运行时， schedule()就会调用该函数，它基本完成两项基本工作：

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

每个进程都有一个 need_resched 标志， 有其他的进程应当被运行， 要尽快被调度。 以前是设置为全局变量， 在 2.2-2.4 在 task_struct 结构体中， 后面被移到thread_info 中。 带内核检查到 need_resched 被设置了， 内核将会尽快调用 schedule() 函数。

访问进程标志符的变量比访问全局变量快(因为current宏的速度很快并且描述符通常存在于高速缓存中)

用于访问和操作need_resched 标志的函数

用户抢占

在内核执行完毕， 即将返回用户空间的时候， 如果 need_resched 被设置， 会导致 schedule() 被调用，此时会发生用户抢占。 因此下面的情况会发生用户抢占：

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

内核抢占

在不支持内核抢占的程序中，内核各个任务之间以协作的方式调度的，不具备抢占性。 内核代码要一直执行完成（返回用户空间）或明显阻塞为止。

Linux 内核支持内核抢占的。 只要进程没有持有锁，就支持内核抢占。 锁是抢占区域的标志。

linux 为每个进程的 thread_info 引入 preempt_count计数器。 该计数器的初始值为0，每当锁使用的时候数值加1， 锁释放的时候数值减1。 当数值为0的时候内核就可以抢占。

从中断返回内核空间的时候，如果 need_resched 被设置且 preempt_count 为0， 表示有任务需要执行并且可以安全的抢占，此时调度程序会被调用。

当然在内核中的进程被阻塞了， 或者它显示的调用 schedlue() 内核抢占都会显示的发生。

因此内核的抢占会发生在：

• 中断处理程序正在执行，返回内核空间以前。
• 内核代码在一次可具备抢占性的时候。
• 如果内核中的任务显示的调用 schedule()
• 如果内核中的任务阻塞（这样会导致调用 schedule（））

实时调度策略

Linux 提供两种实时调度策略：SCHED_INFO 和 SCHED_RR. 和普通的，非实时的调度策略是 SCHED_INFO。

• SCHED_FIFO 是一种简单的，先入先出的调度算法：它不使用时间片。 一旦一个 SCHED_FIFO 级的进程会处于可运行状态， 就会一直执行，直到自己受阻塞或者显示的释放处理器为止；。
• SCHED_RR 类似 SCHED_FIFO ， 只是处于 SCHED_RR级别的进程会分配时间片， 并在时间片耗尽时将不能继续执行。

这两种算法都是静态优先级。

与调度相关的系统调用

Linux 提供了一个系统调用族，用于管理调度程序相关的参数。

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

sched_setscheduler和 sched_setscheduler 用于设置和获取进程的调度策略和实时优先级，他们实现包含许多的参数检查、初始化工作和清理构成的。 其重要的工作在于读取和改写 task_struct的 policy 和 rt_policy 的值。

sched_setparam 和 sched_setparam 用户设置和获取进程的实时优先级。 这两个系统调用用于设置 sched_param 特殊的 `rt_priority.

nice 函数用于给进程的静态优先级添加一个值， 其会设置 task_struct 的 static_prio 值。

与调度器绑定相关的系统调用

Linx 调度程序提供强制的处理器绑定(processor affilinity)机制， 强制指定进程在一些处理器上运行。

struct_task 的 cpu_allowed 的掩码标志的每一位对应着一个系统可用的处理器。 默认情况下， 所有的位被设置， 进程可以在所有的处理器上执行。 用户可以使用 sched_setaffinity 设置不同的一个或几位组合的位掩码。sched_getaffinity 返回当前的位掩码。

内核提供的强制处理器绑定就是设置的 cpu_allowed 并且父进程也会继承子进程的相关的掩码。

放弃处理器时间

sched_yeild() 会显示的将处理器时间让给其他正在执行进程的机制。

第 5 章 系统调用

内核提供一组让用户进程和内核通信的接口， 也就是系统调用。 这些接口有：

• 用户程序有限制的访问硬件资源。
• 提供了创建进程并与已有进程进行通信的功能。
• 提供了申请操作系统其他资源的能力。

与内核通信

系统调用作用：

• 为用户空间提供一组抽象的接口。
• 保证系统的安全和稳定。
• 为用户空间和系统其余部分提供了公共的接口。

第 7 章 中断和中断处理

操作系统一个核心任务就是管理连接到计算机的的设备。 而总所周知外围设备的速度很慢。 通常内核处理器向外围设备发一个请求，在等待硬件设备响应的时候， 内核可以处理其他的任务，等硬件设备真正完成的请求，在对请求进行处理。

有两种方式让处理器和外围设备进行高效的工作：

• 一种是轮询(polling), 是内核定期主动去查询外围设备的状态， 然后进行处理。
• 另外一种是中断机制， 让外围设备主动发出中断信号给内核， 内核根据中断信号进行响应的处理。

中断

中断是本质是硬件设备发出的一种电信号。 中断不必考虑时钟同步， 可以在任何时候产生。

不同设备有不同的中断信号， 操作系统会根据不同的信号调用不同的中断处理程序。

异常是操作系统执行由于编程错误而执行错误的指令时产生， 例如除0，或者缺页， 这时必须要操作系统进行处理时， 就会产生一个异常。 产生异常时必须考虑时钟同步， 因此异常也叫做同步中断。

中断处理程序

产生中断的设备都有一个响应的中断处理程序， 它是设备驱动程序程序(drive)一部分。 而设备驱动程序用于对设备进行管理的内核代码。

中断处理程序和普通内核函数区别不但。 中断程序和其它普通函数的区别在于中断处理程序是由内核调用响应中断的，它们运行在我们称为中断上下文这种特殊的上下文中，并且该上下文中的代码是不可以被阻塞的。 因此中断上下文也称为原子上下文。

中断随时都能够发生， 因此要求中断处理程序能够快速的完成。

上半部和下半部对比

设计中断程序有两个方面：

• 一个是中断处理要运行的快，
• 二是中断处理程序处理的任务要多。

这是一种此消彼长的矛盾关系。 因此把中断程序分为上下两部分：

• 上半部分在接到一个中断， 它仅开始执行有严格时限的工作。 例如中断应答或者硬件复位 。
• 那种能够允许稍后完成的工作会被推后到下半部。

注册中断处理程序

中断程序是管理硬件的驱动程序的一部分。 每个设备都有相关的驱动程序。 当设备需要利用中断， 那么都应该注册一个中断处理程序。 驱动程序可以使用下面的函数注册一个中断处理程序：

1

int request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags, const char *name, void *dev)

• irq 表示要分配的中断号
• handler 是一个指针，指向处理这个中断实际处理程序。

这是处理程序的函数签名：

1

typedef irqreturn_t (*irq_handler_t)(int, void *);

• flag 是一个掩码， 可以下面这些值的组合。

  • IRQF_DISALED——该标志被设置后，意味在内核处理中断处理程序间，要禁止其他所有的中断。
  • IRQF_SAMPLE_RANDOM —— 该标志表示该设备产生的中断对内核的墒池（entropy pool)有贡献。 内核的墒池负责从各种随机中导出真正的随机数。 如果设置了该标志那么个来自该设备的中断间隔时间会作为墒填充到墒池中。
  • IRAQF_TIMER —— 这是为系统定时器特意设置的
  • IRQF_SHARED —— 该标志表明可以在多个中断处理程序中共享中断线。 在同一个给定线的中断处理程序必须设置这个标志， 否则每条线只能有一个处理程序。

• name 表示相关设置额的acii 码表示

• dev 用于共享中断线， 当多个处理程序共享一条中断线时， dev 将提供唯一的标志信息（cookie）， 以便从诸多中断处理程序总移除指定的一个中断处理程序。 如果不共享中断线那么这个值可以为 NULL， 并在内核每次调用中断处理程序时， 都会把dev 传递个中断处理程序。

卸载中断处理程序，会调用下面的函数：

1

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

上面的函数会注销相应的中断处理程序， 并释放中断线。 如果中断线是不共享的，那么dev 可以为 NULL， 否则必须传递 dev ，以删除指定的设备。

中断上下文

进程上下文是内核所处的一种特殊模式， 此时代表内核代表进程执行某些操作——例如执行系统调用或运行内核线程。 在进程上下文中， 可以通过 current 宏关联当前进程。 这样进程就通过进程上下文连接到内核中， 因此处于进程上下文可以休眠也可以调用内核调度程序。

当内核执行一个中断处理程序时， 处于中断上下文中。 中断上下文不与任何进程相关联， 其 current 宏指向被中断的进程， 所以中断上下文不可以被中断， 否则你怎么重新调度它呢。

下半部和推后执行的工作

中断信号随时都能够产生， 因此其可能打断一些比较重要的代码。 并且中断处理程序不与任何进程相关联， 无法被进程调度程序进行重新调度， 因此中断处理程序执行不能够被阻塞的。 因此把一些有时间要求能够快速执行的任务放在中断处理程序放在上半部分（top half）， 较为繁重的没有时限要求的任务放在后半部执行（bottom half）

下半部究竟什么时候执行呢？

下半部强调的并不是立马执行。 下半部不需要指定一个确切的时间， 只是要把这些任务推迟一会儿， 在系统不太繁忙，并且中断恢复后执行就可以了。

通常下半部在中断处理程序返回后一会儿就立即执行。 下半部执行关键在于当它们运行的时候是允许中断的。

下半部的起源

最初 linux 采用 “bottom half” 这种机制来实现下半部， 用于将工作进行推后， 这种机制也称为“BH”。 它提供了一个静态创建，由32个 bottom halves 组成的链表。上半部通过1个32位的整数来标识出那个 bottom half 可以执行，每个 BH 都会在全局范围内进行同步，即使分属不同的处理器，也不允许两个 bottom half 同时执行。

任务队列

任务队列也是用来实现工作推后执行， 用来代替 BH。

软中断和tasklet

第9章 内核同步介绍

临界区和竞争条件

临界区就是访问和操作共享资源的代码片段。

如果存在多个线程访问同一个临界资源， 这说明程序出现了 bug， 这就是竞争条件（race condition）

加锁

给临界资源加上锁上避免出现竞争条件的的一种方法。

锁的作用就是让线程对临界资源的串行访问。

锁有各种形式， 各种锁机制之间的区别在于：当锁被其他线程持有，因而不可用时的行为表现。

• 一些锁在被争用时会简单的执行忙等待。
• 一些锁会让任务睡眠知道锁可用为止。

注意锁是原子操作， 不会出现竞争条件的情况。

死锁

死锁产生需要一定的条件： 要有一个或多个执行线程和一个或多个资源， 每个线程都在等待其中的一个资源，但所有的资源都被占用了。所有的线程都在相互等待， 并且永远不会释放已经咱有的资源。 于是所有的线程都无法继续， 这样死锁就发生了。

自死锁： 一个已持有锁的线程试图去获得一个自己已经持有的锁情况。

有下面的规则避免死锁：

• 按顺序加锁
• 防止发生饥饿（执行的代码一定会执行结束吗）
• 不要重复请求同一个锁
• 设计力求简单（加锁的机制应该简单）

争用和扩展性

锁的争用（loeck contention）简称争用，是只锁被占用的时候， 其他的线程试图获得该锁。

锁处于高度争用状态， 就是指有多个线程正在等待锁。

由于锁的作用是使程序以串行方式访问， 这会降低系统性能。

第 10 章内核同步的方法

第 11 章 定时器和时间管理

时间对linux 内核是非常重要的， 因为内核很多函数都是基于时间驱动的， 当然也有基于事件驱动的。

所有周期的性事件都是由系统定时器驱动的。 系统定时器是一种可编程硬件芯片， 它能够以固定频率产生中断。 该中断就是所谓的定时器中断， 它对应的中断处理器程序负责更新系统时间并负责执行需要周期性需要执行的任务。

系统定时器和时钟中断处理程序是 linux 内核管理机制的中枢。

内核中时间的概念

系统定时器用于计算流逝的时间， 它固定的频率发出时间中断。 这种频率被称作节拍率(tick rate). 当时钟中断发生时， liux 就通过一种特殊的中断处理程序对它进行处理。

时钟预编的节拍率对内核来说是可知， 因此就知道两次时钟的间隔是可知的。 这个时间间隔被称为节拍（tick）

linux 就是靠这种已知的间隔来计算墙上时间（实际时间）和系统运行的时间。

• 系统运行时间表示自系统运行后已经运行了多长时间， 用来计算流逝的时间。
• 实际时间就是现实使用的时间。

节拍率

系统定时器的频率是通过静态预处理定义的， 也就是 HZ。 节拍率被定义在 <asm/param.h> 头文件中定义的。 节拍率在内核编程中是可以修改的， 不是一层不变的。

提高节拍率意味着时钟中断产生的更为频繁，所以中断处理程序会被调用的更加频繁。

高节拍率的优势：

• 内核时钟能够以更高的频度和更高的时间精确度运行。
• 对依赖定时值执行的系统调用， 比如 poll 和 select, 能够以更高的精度运行。
• 对资源的消耗和系统的运行的时间的测量会有更细的解析度。
• 提高进程的抢占精确度。

高节拍率的劣势：

• 节拍率越高，意味着时钟中断的频率越高， 也意味着系统的负载更重。

降低系统节拍还有一个好处就是省电

jiffies

jiffies 是一个全局变量， 用于记录自系统启动以来产生的节拍总数。

jiffy 用于表示时间间隔， 通常是10ms。 在物理学中， 表示光传播一定的距离所花的时间间隔（大抵是1英尺，或者1厘米，或者跨越i个核子）所花的时间。 在计算机中， jiff 通常是两次连续的时钟周期之间的时间。

硬时钟和定时器

计算机中提供了两种设备进行计时， 一种是系统定时器， 一种是实时时钟。

实时时钟

实时时钟（RTC）用来持久存放系统时间的设备， 即便电脑关闭后，它可以靠主板上的微型电池提供的电力保持系统的计时。

在系统启动后， 内核会读取RTC的值来初始化墙上时间（实时时间），该时间存放在xtime 变量中。

系统定时器

各种系统定时器的主要作用是提供一种周期性触发中断的机制。

在X86体系结构中，主要采用可编程中断时钟（PIT）为系统定时器。 PIT 在PC时代就普遍存在， 并且在 DOS 时代就作为中断源。 在内核启动的时候就会对 PIT 进行初始化，时期能够按照HZ/秒的频率产生时钟中断（中断O）。