Linux内核设计与实现[笔记]

发表于 | 更新于: | 分类于 | 本文总阅读量 次
字数统计: 12.2k | 阅读时长 ≈ 44

第 1 章 - Linux 内核简介

1.1 单内核与微内核

概念 优点 缺点
单内核 所有内核服务在一个大内核地址空间运行 1. 简单
2. 高效（内核之间的通信没什么开销，内核可以直接调用函数）		 可用性不好（一个服务影响其他服务）
微内核 1. 微内核的功能被划分成多个独立过程
2. 所有过程运行在自己的地址空间。		 1. 可用性高（一个服务失效并不影响其他服务）
2. 模块化（互换服务）		 消息传递开销大

  • Linux 是单内核，但

    • 包含了微内核的精华：模块化 + 抢占式内核 + 内核线程 + 动态装载内核模块

    • 避免了微内核的缺陷：所有事情运行在内核态，无需消息传递

1.2 Linux 内核与传统 Unix 系统之间的差异

  • Linux 支持动态加载内核模块
  • Linux 支持对称多处理机制（SMP）
  • Linux 内核支持抢占
  • Linux 内核不区分线程和其他的一般进程（对于内核来说，所有进程都一样，只不过是其中的一些共享资源而已）
  • Linux 提供了具有设备类的面向对象的设备模型、热插拔事件，以及用户空间的设备文件系统（sysfs）

1.3 Linux 内核版本

由四个数字组成

  • 主版本号：偶数代表稳定版；奇数代表开发版
  • 第四个数字可选，表示稳定版本号。包含了关键性 bug 的修改，是为了解决版本发布周期过长的副作用，更利于系统的稳定性。

第 2 章 - 从内核出发

2.1 获取内核源码

https://www.kernel.org/

旧版 Index of /pub/linux/kernel/ 这里下载 linux-2.6.26.tar.gz

注意：内核源码一般安装在 `/usr/src/linux` ，应建立自己的主目录对内核进行修改然后用 root 身份安装，而不是以 root 身份对 `/usr/src/linux` 目录进行修改。

2.2 内核源码树

目录 描述
arch 特定体系结构的源码
block 块设备 I/O 层
crypto 加密 API
Documentation 内核源码文档
drivers 设备驱动程序
firmware 设备驱动需要的设备固件
fs 文件系统
include 内核头文件
init 内核引导和初始化
ipc 进程间通信代码
kernel 核心子系统（如调度程序）
lib 通用内核函数
mm 内存管理子系统和 VM
net 网络子系统
samples 示范代码
scripts 编译内核所用的脚本
security Linux 安全模块
sound 语音子系统
usr 早期用户空间代码
tools Linux 开发工具
virt 虚拟化基础结构

2.3 编译内核

  • 如何减少编译的垃圾信息？

    将无用信息重定向到永无返回值的黑洞

1
make > /dev/null

  • 以多个作业编译内核

    n 代表要衍生的作业数，每个处理器一般衍生一个或两个作业。如在 16 核处理器上，可以 make -j32

1
make -jn > /dev/null

2.4 内核开发的特点

  1. 内核编程时，不能访问 C 库，和标准的 C 头文件（因为效率低。不过大部分常用 C 库函数在内核都实现了）
  2. 必须使用 GNU C
  3. 没有内存保护机制
  4. 不使用浮点数运算
  5. 每个进程只有一个很小的定长堆栈
  6. 注意同步和并发（内核容易发生竞争，解决竞争：自旋锁和信号量）
  7. 注重可移植性

第 3 章 - 进程管理

3.1 进程（也即：任务 task）

进程的两种虚拟机制：虚拟处理器和虚拟内存

  • 虚拟处理器：让进程觉得自己独享处理器
  • 虚拟内存：让进程觉得自己拥有所有内存资源
注意：同一进程中的**线程**之间可以共享虚拟内存，但是每个都拥有自己的虚拟处理器

3.2 进程描述符和任务结构

3.2.1 进程描述符的组成

内核把进程列表存放在双向循环链表——任务队列中，链表每一项都是进程描述符的结构体 task_struct 。具体细节在 linux-2.6.26/include/linux/sched.h，进程描述符包含的数据有：

  • 打开的文件
  • 进程的地址空间
  • 挂起的信号
  • 进程状态
  • 进程间的关系等

image-20210628230358383

Linux 通过 slab 分配器分配 task_struct 结构。

3.2.2 五种进程状态

  • TASK_RUNNING 运行
  • TASK_INTERRUPTIBLE 可中断
  • TASK_UNINTERRUPTIBLE 不可中断
  • __TASK_TRACED 被跟踪
  • __TASK_STOPPED 停止

3.2.3 进程家族树

  • 所有进程都是 PID 为 1 的 init 进程的后代。内核在系统启动的最后阶段启动 init 进程。

3.3 进程创建

3.3.1 主要函数

  • fork()：拷贝当前进程创建一个子进程
  • exec()：读取可执行文件并将其载入地址空间开始执行
拓展
  • fork 中的拷贝是写时拷贝：只有在需要写入时，数据才会被复制。（避免拷贝大量根本用不到的数据）
  • fork 的实际开销：复制父进程的页表 + 给子进程创建唯一的进程描述符

fork 的具体流程

1
2
3
fork() 调用 clone()
clone() 调用 do_fork()
do_fork() 调用 copy_process()

copy_process() 拷贝或共享打开的文件、文件系统信息、信号处理函数、进程地址空间、命名空间等。如果 copy_process() 成功返回，新创建的子进程被唤醒并投入使用。内核首先执行子进程，因为一般子进程会立马调用 exec() ，这样可以避免写时复制的额外开销。（如果先执行父进程，有可能会开始向地址空间写入）

拓展
  • vfork() 与 fork() 的区别

vfork() 不拷贝父进程的页表项

3.4 Linux 的内核线程

  • 从内核角度看，并没有线程的概念，Linux 把所有的线程都当作进程实现。线程被视为一个与其他进程共享某些资源的进程。

  • 内核线程与普通的进程间的区别：内核线程没有独立的地址空间，只在内核空间运行，从不切换到用户空间。

  • 内核进程和普通进程一样，可被调度，可被抢占。

3.5 进程的终止

大部分都要靠 do_exit() 完成，do_exit() 做了一系列工作以后调用 schedule() 切换到新的进程。然后与进程相关联的所有资源就都被释放掉了。但是进程本身占用的内存还需要等父进程释放。

注意：do_exit() 永不返回

3.5.1 孤儿进程

  • 产生原因：父进程在子进程之前退出，就会产生孤儿进程。

  • 解决方法：给子进程在当前线程组找一个爹，找不到就让 init 进程做爹。然后再调用 wait()

第 4 章 - 进程调度

进程调度的作用：决定在什么时间让什么进程运行。

4.1 多任务系统

  • 非抢占式：除非自己停止，不然就一直执行。
  • 抢占式（绝大多数）：调度程序可以强制挂起一个程序，让其他程序执行。

4.2 调度策略

调度策略需要在进程响应迅速（响应时间）和最大系统利用率（吞吐量）之间寻找平衡。Linux 对进程响应做了优化（缩短响应时间），更倾向于优先调度 I/O 消耗型进程。

4.2.1 基于优先级的调度

两种不同的优先级范围
度量方法 范围 含义
nice 值 [-20,19] 默认为 0 1. nice 越低，优先级越高
2. 在 Linux 系统中，nice 值代表时间片的比例
实时优先级 [0,99] 值最高，进程优先级越高
  • 查看进程的 nice 优先级（NI） 和 实时优先级（RTPRIO），- 表示不是实时进程
1
ps -eo state,uid,pid,ppid,ni,rtprio,time,comm

image-20210629104007997

时间片的长与短

时间片是一个数值，表示进程被抢占前能持续运行的时间。

  • 过长：系统响应变慢
  • 过短：增大进程切换导致的处理器耗时

4.3 Linux 调度算法

4.3.1 完全公平调度算法 CFS

Completely Fair Scheduler，相关代码位于 kernel/sched_fair.c ，CFS 允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程。

a. CFS 的公平体现在哪
  • CFS 确保给每个进程公平的处理器使用比。（这个处理器使用比如何得到？nice 值：任何进程获得的处理器时间由自己和其他进程 nice 值得相对比例决定。nice 对应得时间不再是绝对值，而是处理器使用比）
b. CFS 的实现

  1. 时间记账 （通过 update_curr() 更新 vruntime ）

    虽然 CFS 没有时间片概念，但为了确保每个进程只在公平分配的处理器时间内运行，还是要维护每个进程运行的时间记账。CFS 通过调度器实体结构 sched_entity 追踪进程运行记账。

    • 该结构体中有一个虚拟实时变量 vruntime 存放进程的虚拟运行时间。CFS 使用 vruntime 记录一个程序运行了多长时间以及还要运行多久。

  2. 进程选择

    CFS 核心：选择 vruntime 最小的任务。选择算法通过红黑树实现：运行红黑树最左边叶子节点代表的那个进程。具体实现在 kernel/sched_fair.c 的 __pick_next_entity() 函数。

  3. 调度器入口 schedule()

    schedule() 函数会调用 pick_next_task() ，选择最高优先级的进程

  4. 睡眠和唤醒

    唤醒通过 wake_up() 调用 try_to_wake_up() 实现。

4.4 抢占

4.4.1 什么情况产生用户抢占

  1. 从系统调用返回用户空间时
  2. 从中断处理程序返回用户空间时

4.4.2 什么情况发生内核抢占

  1. 中断处理程序正在执行，且返回内核空间前
  2. 内核代码再次具有抢占性的时候
  3. 内核中的任务显示调用 schedule()
  4. 内核中的任务阻塞（同样会调用 schedule()）

4.5 与调度相关的系统调用

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

系统调用 描述
nice() 设置进程 nice 值
sched_setscheduler() 设置进程调度策略
sched_getscheduler() 获取..
sched_setparam() 设置进程实时优先级
sched_getparam() 获取..
sched_get_priority_max() 获取实时优先级最大值
sched_get_priority_min() 获取实时优先级最小值
sched_rr_get_interval() 获取进程的时间片值

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

系统调用 描述
sched_setaffinity() 设置进程的处理器的亲和力
sched_getaffinity() 获取..
sched_yield() 暂时让出处理器

第 5 章 - 系统调用

5.1 系统调用的作用

系统调用相当于在用户进程和硬件设备之间加了中间层。其作用包括：

  1. 为用户空间提供一种硬件的抽象接口。
  2. 保证系统稳定和安全。
  3. 为了实现多任务和虚拟内存。

系统调用是用户空间访问内核的唯一手段；除异常和陷入外，系统调用是内核的唯一合法入口。
Linux 中，每个系统调用都被赋予一个系统调用号，系统调用号一旦分配就不会变，内核记录了系统调用表中的所有已注册的系统调用的列表 sys_call_table

5.2 如何通知内核，自己要执行系统调用？

通知内核的机制靠软中断实现：引发一个异常促使系统切换到内核态，然后去执行异常处理程序（此时实际上就是**系统调用处理程序 system_call()**）。 * 知识点 一：如何触发软中断？

x86 系统预定义的软中断是中断号 128 ，通过 int &0x80 或 sysenter 指令触发，后者更快。

  • 知识点 二：通过软中断陷入内核空间（执行系统调用处理程序）后，如何指定恰当的系统调用？

x86 系统通过 eax 寄存器将系统调用号传给内核。

5.3 系统调用的实现

虚构一个系统调用 foo() 来观察系统调用的实现步骤

  1. 首先，把新的系统调用 sys_foo() 加入系统调用表的末尾。

    大多数体系结构的系统调用表位于 entry.s，Linux 2.6 的系统调用表在 linux-2.6.26/arch/x86/kernel/syscall_table_32.S 中

    • 查找方法及结果
1
grep "ENTRY(sys_call_table)" -R .

image-20210629173934526

image-20210629173436618

  • 在末尾添加
1
.long sys_foo 			/* my_sys_call */

image-20210629174223271

所以我们新添加的系统调用的调用号为 327

  1. 把系统调用号加入 asm/unistd.h，Linux 2.6 对应的文件为 linux-2.6.26/include/asm-x86/unistd_32.h

    • 查找方法
    1
    grep "#define __NR_restart_syscall" -R .

    image-20210629174858689

  • 在该列表中加入下面这行
1
#define __NR_foo		327

image-20210629175039385

  1. 实现 foo() 系统调用。该系统调用必须编译到核心的内核映像中，所以该例我们将其放到 kernel/sys.c 中。当然，如果其功能与调度相关，也可以放到 kernel/sched.c 中，类比书中 P66 的代码
1
find . | grep page.h

有

image-20210629193023117

  • 修改代码如下，将代码添加到 linux-2.6.26/kernel/sys.c 中
1
2
3
4
5
6
7
#include <asm-x86/page.h>

// 返回每个进程的内核栈大小
asmlinkage long sys_foo(void)
{
    return THREAD_SIZE;
}

5.4 从用户空间访问系统调用

参考 基于ubuntu14.04下编译linux2.6内核_pleasecallmekaige的博客-CSDN博客

  • 编译修改后的内核代码 
1
make menuconfig

报错

1
2
3
Makefile:434: *** mixed implicit and normal rules: deprecated syntax
Makefile:1550: *** mixed implicit and normal rules: deprecated syntax
make: *** No rule to make target 'menuconfig'.  Stop.

解决报错参考

首先，将 434 行的 

1
config %config: scripts_basic outputmakefile FORCE

改为

1
%config %config: scripts_basic outputmakefile FORCE

image-20210629202320129

再将 1550 行的

1
/ %/: prepare scripts FORCE

改为

1
%/: prepare scripts FORCE

然后重新 make menuconfig

  • 未完待更新

第 6 章 - 内核数据结构

6.1 链表

内核链表代码在 include/linux/list.h （如 linux-2.6.26/include/linux/list.h）

image-20210630175047243

内核提供了一组函数来操作链表

函数 作用
list_add(struct list_head new, struct list_head head); 在 head 后插入 new 节点
list_del(struct list_head *entry); 在链表中删除 entry 元素
注意：这个操作并不会释放 entry 或 包含 entry 的数据结构占用的内存，只是将 entry 移除链表。
list_move(struct list_head list, struct list_head head) 从一个链表中移除 list，并将其加入另一个链表的 head 节点后面
list_move_tail(struct list_head list, struct list_head head) 移到 head 前（链表的末尾）
list_empty(struct list_head *head) 检查链表是否为空
list_splice(struct list_head list, struct list_head head) 将 list 指向的链表插入到指定链表的 head 元素后面
list_splice_init(struct list_head list, struct list_head head) 同上，唯一区别是：由 list 指向的链表要被重新初始化

6.2 队列

Linux 内核通用队列实现称为 kfifo。其实现在 kernel/kfifo.c ，声明在 include/linux/kfifo.h 中。

6.3 映射

6.4 红黑树

红黑树的属性

  1. 所有节点非黑即红
  2. 叶子节点都是黑色
  3. 叶子节点不包含数据
  4. 所有非叶子节点都有两个子节点
  5. 如果一个节点是红色，则它的子节点都是黑色
  6. 在一个节点到其叶子节点的路径中，如果总包含相同数目的黑色节点，那该路径是最短的

所以，最深的叶子节点的深度不会大于两倍的最浅叶子节点的深度。

Linux 实现的红黑树称为 rbtree，定义在 lib/rbtree.c ，声明在文件 include/linux/rbtree.h

第 7 章 - 中断和中断处理

7.1 中断的分类

  1. 同步中断（也即异常）：由处理器本身产生
  2. 异步中断：由硬件产生

7.2 中断处理程序的特点

  • 中断处理程序与其他内核函数的区别？

    中断处理程序被内核调用来响应中断，它运行在中断上下文（原子上下文）中，该上下文中的执行代码不可阻塞。

7.3 中断处理的上半部与下半部

  • 中断处理程序是上半部（top half）：接收到一个中断就立即执行，但只做有严格实现的工作（比如对接受的中断进行应答或复位硬件）。

  • 下半部是一些能够被允许稍后完成的工作。

7.4 注册中断处理程序

  • 设备使用中断时，会发生什么？

如果设备使用中断，那相应的驱动程序就通过 request_irq() 函数注册一个中断处理程序，并激活给定的中断线以处理中断。（该函数声明位于 <linux/interrupt.h>，具体如下）

1
2
3
4
5
6
7
8
9
10
11
12
/* request_irq 注册函数，分配一条给定的中断线，若成功执行则返回 0
 * irq       - 要分配的中断号
 * handler   - 指向实际处理这个中断的中断处理程序的指针
 * flags     - 中断处理程序标志位
 * name      - 中断相关的设备名称 ASCII 表示
 * dev       - 用于共享中断线
 */
int request_irq(unsigned int irq,
                irq_handler_t handler,
                unsigned long flags,
                const char *name,
                void *dev)
  • 中断处理程序标志
标志位 含义
IRQF_DISABLED 内核在处理中断处理程序本身期间，要禁止所有的其他中断
IRQF_SAMPLE_RANDOM 表明设备产生的中断对内核熵池有贡献
IRQF_TIMER 为系统定时器的中断处理准备的
IRQF_SHARED 表示可以在多个中断处理程序之间共享中断线

7.5 释放中断处理程序

  • 卸载驱动程序时，需要注销相应的中断处理程序，并释放中断线。
1
void free_irq(unsigned int irq, void *dev)  // 注销函数

7.6 中断上下文

进程上下文 中断上下文
可以通过 current 宏关联当前上下文 与 current 宏不相关（尽管它会指向被中断的进程）
可以睡眠 不可以睡眠
  • 中断上下文有较为严格的时间限制（因为它打断了其他代码）
  • 中断上下文的代码应当迅速，简洁（同上）
  • 尽量把工作分离出来，放到下半部执行，因为下半部可以在更适合的时间运行

7.7 中断处理机制的实现（中断从硬件到内核的路由）

image-20210702151130093

  1. 硬件产生中断，通过总线把电信号传给中断控制器
  2. 如果中断线是激活的，中断就会被传给处理器

中断处理机制中，内核调用的函数涉及：

函数 含义
do_IRQ() 提取中断的值，对接收的中断进行应答
handle_IRQ_event() 运行当前中断线所安装的中断处理程序（定义在 kernel/irq/handler.c）
ret_from_intr() 1. 如果重新调度正在被挂起，
 a. 且内核正在返回用户空间（即中断了用户进程），则调用 schedule()
 b. 且内核正在返回内核空间（即中断了内核本身），则只有在 preempt_count 为 0 时，才调用 schedule()
2. 未被挂起，则恢复原来的寄存器，内核恢复到曾经中断的点

拓展 - procfs 虚拟文件系统

procfs 只存在于内核内存，一般位于 /proc 目录，procfs 中读写文件都要调用内核函数。/proc/interrupts 存放的是系统中与中断相关的统计信息

具体如下图示

注意因为这里试验机有两个处理器，所以部分列会多一列出来

  • 第一列：中断线
  • 第二列：一个接收中断数目的计数器
  • 第三列：中断控制器
  • 第四列：设备名

image-20210702152502338

7.8 中断控制方法

可以禁止当前处理器的中断系统或屏蔽一条中断线。具体接口可以在 <asm/system.h> 和 <asm/irq.h> 找到。

函数 说明
local_irq_disable() 禁止本地中断传递
local_irq_enable() 激活本地中断传递
local_irq_save() 保存本地中断传递的当前状态，然后禁止本地中断传递
local_irq_resotre() 恢复本地中断传递到给定状态
disable_irq() 禁止给定中断线，并确保该函数返回之前在该中断线上并没有处理程序在运行
disable_irq_nosync() 禁止给定中断线
enable_irq() 激活给定中断线
irqs_disabled() 本地中断传递被禁止，则返回 0；否则非 0
in_interrupt() 1. 在中断上下文，则返回非 0
2. 在进程上下文，则返回 0
in_irq() 1. 当前正在执行中断处理程序，返回非 0
2. 不在执行，返回 0

第 8 章 - 中断处理的下半部工作

8.1 为什么将中断处理流程分成上下两个部分？

因为中断处理程序本身是有局限的。

  1. 中断处理程序越快越好

    • 中断处理程序异步执行，有可能会打断某些重要代码，为避免被打断的代码停止时间过长，就需要中断处理程序越快越好
    • 为防止太多其他中断被屏蔽，而导致硬件与操作系统无法通信，中断处理程序需要越快越好
    • 中断处理程序往往要操作硬件，所以有很高的时限要求

  2. 中断处理程序不在进程上下文中运行，所以不能阻塞。

所以，中断处理程序只能实现那些时间要求很严格的操作，其他操作就被退后到中断被激活以后再运行。

8.2 下半部做哪些工作？

中断处理程序以外的工作。那先大致捋一下**中断处理程序工作范畴** 1. 对时间非常敏感的 2. 跟硬件相关的 3. 要保证不被其他中断打断的 ### 8.3 下半部的实现机制 上半部的实现机制只有一种，那就是中断处理程序。下半部的实现机制包括： 1. 软中断 softirqs （编译期间静态分配） 2. tasklet （最常用，通过软中断实现。动态注册） 3. 工作队列 work queues
下半部机制 上下文 顺序执行保障 复杂程度 性能
软中断 中断 没有 高 好
tasklet 中断 同类型不能同时执行 中等 中等
工作队列 进程 没有（和进程上下文一样被调度） 简单 差（开销最大）

8.3.1 软中断的实现与使用

实现

kernel/sofrirq.c 中实现

  1. 软中断处理程序 action 的函数原型： 
1
void softirq_handler(struct softirq_action *)

一个软中断不会被另一个软中断抢占，只会被中断处理程序抢占。不过其他软中断可以在其他处理器同时执行

  1. 执行软中断
使用
  1. 分配索引

    内核用从 0 开始的索引表示优先级，索引值越小，优先级越高。如果想自己建立新的软中断，就要在这个表示索引的枚举类型中加入对应的项，由于索引值与优先级相关，所以还不能随便加，应根据优先级确定加入的位置。（这个枚举类型在 <linux/interrupt.h）习惯上，HI_SOFTIRQ 在第一项，RCU_SOFTIRQ 在最后一项，新加入的软中断对应索引一般在 BLOCK_SOFTIRQ 和 TASKLET_SOFTIRQ 之间。

    • tasklet 类型列表
tasklet 优先级 软中断描述
HI_SOFTIRQ 0 优先级高的 tasklets
TIMER_SOFTIRQ 1 定时器的下半部
NET_TX_SOFTIRQ 2 发送网络数据包
NET_RX_SOFTIRQ 3 接收网络数据包
BLOCK_SOFTIRQ 4 BLOCK 装置
TASKLET_SOFTIRQ 5 正常优先级的 tasklets
SCHED_SOFTIRQ 6 调度程度
HRTIMER_SOFTIRQ 7 高分辨率定时器
RCU_SOFTIRQ 8 RCU 锁定

  1. 通过 open_softirq() 注册软中断处理程序。

    这个函数有两个参数：软中断的索引号，处理函数

  2. 触发软中断

    经过枚举类型添加新项和注册，新的软中断处理程序就可以运行了。raise_softirq() 可以将一个软中断设置为挂起状态，让它下次调用 do_softirq() 即可投入使用。

8.3.2 tasklet

结构体及值的说明

tasklet 由软中断实现，本质相似，但接口更简单，锁保护要求更低。

tasklet 结构体定义在 <linux/interrupt.h> 

1
2
3
4
5
6
7
8
struct tasklet_struct
{
	struct tasklet_struct *next;  // 链表中的下一个 tasklet
	unsigned long state;  // tasklet 状态
	atomic_t count;  // tasklet 引用的计数武器
	void (*func)(unsigned long);  // tasklet 处理函数
	unsigned long data;  // 给 tasklet 处理函数的参数
};

tasklet 状态值（state）：

状态值 说明
0 未被调度
TASKLET_STATE_SCHED tasklet 已调度，正准备投入运行
TASKLET_STATE_RUN tasklet 正在运行

计数器值（count）：

计数器值 说明
非 0 tasklet 被禁止，不允许执行
0 tasklet 被激活，并被设为挂起状态，可执行
所有的 tasklet 都通过重复运用 HI_SOFTIRQ 和 TASKLET_SOFTIRQ 这两个软中断实现。

一个 tasklet 被调度，内核就会唤醒这两个软中断中的一个

使用 tasklet

  1. 声明

    静态声明

1
DECLARE_TASKLET(my_tasklet, my_tasklet_handler, dev);

等价于

1
2
struct tasklet_struct my_tasklet = {NULL, 0, ATOMIC_INIT(0),
                                   	my_tasklet_handler, dev};

​ 动态声明

1
tasklet_init(t, tasklet_handler, dev);
  1. 编写自己的 tasklet 处理程序
1
void tasklet_handler(unsigned long data)
  1. 调度自己的 tasklet
1
tasklet_schedule(&my_tasklet);  /* 把 my_tasklet 标记为挂起 */
内核是如何处理软中断的？

方案说明

方案 说明 优 缺
一 本次执行全部处理（只要还有被触发并等待处理的软中断，本次执行就要负责处理，重新触发的软中断也在本次执行返回前被处理） 可以即时处理内核的软中断 负载较高时，会有大量重复触发的软中断，用户空间的任务就会被忽略（用户空间处于饥饿状态）
二 不处理重新触发的软中断（等下一个软中断执行去处理） 用户不饥饿了 软中断可能饥饿
三 折中。
1. 不立即处理重新触发的软中断
2. 大量软中断出现时，内核唤醒一组低优先级的内核线程来处理这些负载。		 1. 负载高，用户也不会饥饿
2. 空闲时，软中断处理也很快

8.3.3 工作队列 work queue

  1. 特点

    • 靠内核线程实现

    • 可以将工作推后执行，交由一个内核线程去执行

    • 工作队列允许重新调度，甚至睡眠

  2. 怎么在工作队列和软中断/tasklet 中做选择？

    • 看推后执行的任务，是否需要睡眠。要睡眠就工作队列。

    • 是否需要重新调度，需要则工作队列

    如果不需要用一个内核线程来推后执行工作，就还是选 tasklet

第 9 章 - 内核同步介绍

  • 为什么要做内核同步？

    防止共享资源并发访问。（并发访问，可能会发生各线程间相互覆盖共享数据的情况。这会导致系统不稳定，且问题不好定位）

9.1 临界区和竞争条件

  • 临界区：临界段，就是访问和操作共享数据的代码段。

  • 竞争条件：两个线程在同一临界区同时执行，就存在竞争。

9.2 锁机制

  • 本质：给临界区加锁，保证临界区只存在一个执行线程。

image-20210706155926907

  • 锁机制之间的主要区别

    一些锁被争用时，就简单执行忙等待；另外一些锁会使当前任务睡眠直到锁可用。

  • 造成并发执行的原因

竞争条件成因 说明
中断 中断随时可能发生，可能随时打断正在执行的代码
软中断和 tasklet 内核能随时可能唤醒或调度软中断和 tasklet，也就随时可能打断正在执行的代码
内核抢占 内核具有抢占性，内核中的任务可能会被另一个任务抢占
睡眠及与用户空间的同步 在内核执行的进程可能会睡眠，这就会唤醒调度程序，从而导致调度一个新的用户进程执行
对称多处理 多个处理器同时执行代码

编写内核代码时需要考虑的问题

  1. 这个数据是不是全局的？除了当前线程外，其他线程能不能访问它？
  2. 这个数据会不会在进程上下文和中断上下文中共享？它是不是要在两个不同的中断处理程序中共享？
  3. 进程在访问数据时有没有可能被抢占？被调度的新程序会不会访问同一数据？
  4. 当前进程会不会睡眠（阻塞）在某些资源上，如果会，它会让共享数据处于何种状态？
  5. 怎样防止数据失控？
  6. 如果这个函数又在另一个处理器上被调度将会发生什么？
  7. 如何确保代码远离并发威胁？

9.3 死锁

  • 发生死锁的原因

    每个线程都在相互等待，但是所有资源都被占用了，它们也不释放已经占用的资源，导致任何线程都无法继续，因此产生死锁。

9.3.1 实例

  • 最简单的死锁：自死锁

一个执行线程想获得自己已经拥有的锁，它就等待这个锁，但是自己又不会释放这个锁，最终导致死锁。

  • 常见的 ABBA 锁

image-20210706164827753

9.3.2 如何避免死锁

  1. 按顺序加锁（最重要）
  2. 防止发生饥饿
  3. 不重复请求同一个锁
  4. 设计力求简单（越复杂的加锁方案越容易死锁）

9.4 加锁粒度

  • 加锁机制发展到细粒度（fine-grained）加锁后，有什么好处？

    Linux 从 2.0 版内核，刚加入对多处理器支持的时候，一个时刻只能有一个任务在内核中执行。2.2 版本加锁机制发展到细粒度加锁后，不再有这样的限制。

  • 粒度的粗细，有什么影响？

加锁粒度 扩展性 复杂度 开销 加锁保护的数据规模
粗 差 低 小 大
细 好 高 大 小
  • 锁的争用：锁正被占用时，有其他线程试图获得该锁。

第 10 章 - 内核同步方法

简单场景：临界区只有一个变量 - 原子操作

复杂场景 - 锁机制

10.1 原子操作

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

  • 原子操作通常是内联函数，往往通过内联汇编指令来实现。

原子整数操作的声明在 <asm/atomic.h> 中。

原子位操作定义在 <asm/bitops.h> 中

10.2 自旋锁

Linux 内核最常见的锁。

10.2.1 特点

  1. 自旋锁最多只能被一个可执行线程持有（如果一个执行线程试图获得一个被占用的自旋锁，该线程就会一直循环-旋转-等待锁重新可用）

  2. 一个被争用的自旋锁，会让请求它的线程在等待锁重新可用时自旋，特别浪费处理器时间，这是自旋锁的要点

    所以，自旋锁不应该被长时间持有。自旋锁的初衷就是：在短期内进行轻量级加锁。

10.2.2 自旋锁方法

自旋锁与体系结构相关的代码定义在 <asm/spinlock.h> 中，接口定义在 <linux/spinlock.h> 中。

注意

  1. 自旋锁不能递归，否则自死锁

  2. 在中断处理程序中使用自旋锁时，一定要在获取锁之前，首先禁止本地（当前处理器的）中断（否则造成 ABBA 锁）

    解释一下为什么会造成 ABBA 锁：中断处理程序试图获得这个已经被持有的锁，就会自旋，等待锁重新可用，但这个锁的持有者在中断处理程序执行完以前不可能运行，自然不会释放锁。

  • 自旋锁方法列表
方法 描述
spin_lock() 获取指定的自旋锁
spin_lock_irq() 禁止本地中断并获取指定的锁
spin_lock_irqsave() 保存本地中断的当前状态，禁止中断，获取指定的锁
spin_unlock() 释放指定的锁
spin_unlock_irq() 释放指定的锁，并激活本地中断
spin_lock_init() 动态初始化指定的 spinlock_t
spin_trylock() 试图获取指定的锁，未获取则返回非 0
spin_is_lock() 如果指定的锁当前正在被获取，则返回非 0

10.2.3 自旋锁与下半部的配合使用

  1. 因为下半部可以抢占进程上下文中的代码，所以下半部和进程上下文共享数据时，要保护进程上下文中的数据：加锁并禁止下半部执行

  2. 中断处理程序可以抢占下半部，所以中断处理程序和下半部共享数据时，在获取锁的同时还要禁止中断

  3. 同类的 tasklet 不可能同时运行，所以同类 tasklet 的共享数据不需要保护。但不同类的 tasklet 共享时，访问下半部数据前要先获得一个普通的自旋锁 （这里不用禁止下半部，因为同一处理器不存在 tasklet 相互抢占的情况）
  4. 数据被软中断共享，必须加锁保护，但不必禁止下半部（无论软中断是否同类型，因为同一处理器的软中断不会相互抢占）

10.3 读-写自旋锁

多个读任务可以并发持有读者锁，但用于写的锁只能被一个写任务持有。读锁被持有时，写操作只能等待；而读者可以继续成功占用锁。读/写锁也叫共享/排斥锁，或者并发/排斥锁。通常情况下，读锁和写锁位于完全分隔开的代码分支中。

  • 读-写锁方法
方法 描述
read_lock() 获得指定的读锁
read_lock_irq() 禁止本地中断并获得指定读锁
read_lock_irqsave() 存储本地中断的当前状态，禁止本地中断并获得指定读锁
read_unlock() 释放指定的读锁
read_unlock_irq() 释放指定的读锁，并激活本地中断
read_unlock_irqstore() 释放指定的读锁，并将本地中断恢复到指定的前状态
write_lock() 获得指定的写锁
write_lock_irq() 禁止本地中断并获得指定写锁
write_lock_irqsave() 存储本地中断的当前状态，禁止本地中断并获得指定写锁
write_unlock() 释放指定的写锁
write_unlock_irq() 释放指定的写锁，并激活本地中断
write_unlock_irqstore() 释放指定的写锁，并将本地中断恢复到指定的前状态
write_trylock() 试图获得指定的写锁；如果写锁不可用，返回非 0 值
rwlock_init() 初始化指定的 rwlock_t
  • 自旋锁与信号量的使用场景有何不同？

自旋锁：加锁时间不长，且代码不会睡眠（比如中断处理程序）

信号量：加锁时间很长，代码在持有锁时可能睡眠

10.4 信号量

Linux 中的信号量是一种睡眠锁。原理：任务试图获得一个被占用的信号量，信号量将其推进一个等待序列并让其睡眠，这样处理器就可以空闲并执行其他代码，当那个信号量可用的时候，等待序列中的那个任务就会被唤醒并获得该信号量。

  • 自旋锁与信号量区别
锁 处理器利用率 开销
自旋锁 低 小
信号量 高 大

10.4.1 信号量的分类

信号量同时允许的持有者数量可以在声明信号量时指定，根据这个数量，可分为二值信号量和计数信号量。

  • 二值信号量（也即互斥信号量）：只有 0 和 1 两种情况

  • 计数信号量：数量可以大于 1，也就是说，允许同一时刻允许多个持有者，也即允许多个执行线程同时访问临界区。

内核使用信号量时，基本都是用互斥信号量

10.4.2 信号量的创建与使用

信号量的实现与体系结构相关，在 <asm/semaphore.h> 中。

几种创建方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * name     - 信号量变量名
 * count    - 信号量的使用数量
 * sem      - 指向动态创建的信号量的间接指针
 */
// 静态声明计数信号量
struct semaphore name;
sema_init(&name, count);

// 静态创建互斥信号量
static DECLARE_MUTEX(name);

// 更常见的情况，信号量作为一个大数据结构的一部分，动态创建
sema_init(sem, count);

// 与上一条类似，初始化一个动态创建的互斥信号量
init_MUTEX(sem);
常规使用方法
1
2
3
4
5
6
7
8
9
10
/* 定义并声明一个信号量，名为 mr_sem，用于信号量计数 */
static DECLARE_MUTEX(mr_sem);

/* 试图获取信号量 */
if (down_interruptible(&mr_sem))

/* 临界区... */

/* 释放给定的信号量 */
up(&mr_sem);
  • 信号量方法列表
方法 描述
sema_init(struct semaphore *, int) 以指定的计数值初始化动态创建的信号量
init_MUTEX(struct semaphore *) 以计数值 1 初始化动态创建的信号量
init_MUTEX_LOCKED(struct semaphore *) 以计数值 0 初始化动态创建的信号量（初始为加锁状态）
down_interruptible(struct semaphore *) 试图获得指定的信号量，若被占用，则进入可中断睡眠状态
down(struct semaphore *) 试图获得指定的信号量，但是如果被占用，会进入不可中断睡眠
down_trylock(struct semaphore *) 试图获得指定的信号量，被占用，则返回非 0 值
up(struct semaphore *) 释放指定信号量，如果睡眠队列不空，则唤醒其中一个任务

10.5 读-写信号量

读写信号量与信号量的关系类似读写自旋锁与自旋锁的关系。

10.5.1 读-写信号量的特点

  1. 所有的读-写信号量都是互斥信号量（当然只对写者互斥，不对读者）

  2. 不会被信号打断

  3. 读-写信号量比读-写自旋锁多一种特有操作: downgrade_write() ，可以将动态获取的写锁转换成读锁

需要注意，除非代码中读和写可以清楚地分开，否则最好不使用。

10.6 互斥体 mutex

☞任何可以睡眠的强制互斥锁。mutex 的使用场景更严格

  1. mutex 的使用计数永远是 1
  2. 需在同一个上下文加解锁
  3. 不允许递归上锁和解锁
  4. 持有 mutex 的进程不能退出
  5. mutex 不能在中断或者下半部使用
  6. mutex 只能通过官方 API 管理

Mutex 方法

方法 描述
mutex_lock(struct mutex *) 为指定的mutex上锁，如果锁不可用则睡眠
mutex_unlock(struct mutex *) 为指定的mutex解锁
mutex_trylock(struct mutex *) 试图获取指定的mutex，如果成功则返回1；否则锁被获取，返回0
mutex_is_locked(struct mutex *) 如果锁已被争用，则返回1；否则返回0

10.6.1 信号量与互斥体怎么选？

优先使用 mutex，如果不能满足某些约束条件，再考虑信号量

10.6.2 自旋锁与互斥体怎么选？

需求 加锁方法
低开销加锁 优先自旋锁
短期锁定 优先自旋锁
中断上下文加锁 只能自旋锁
长期加锁 优先互斥体
持有锁需要睡眠 只能互斥体

10.7 完成变量

completion variable，提供了代替信号量的一种简单方法。如果在内核中一个任务需要发出信号通知另一个任务发生了某个特定事件，完成变量是使两个任务同步的简单方法。

完成变量由 completion 结构表示，定义在 <linux/completion.h> 中，完成变量方法有：

方法 描述
init_completion(struct completion *) 初始化指定的动态创建的完成变量
wait_for_completion(struct completion *) 等待指定的完成变量接受信号
complete(struct completion *) 发信号唤醒任何等待任务

使用完成变量的例子可以参考 kernel/sched.c 和 kernel/fork.c

10.8 BLK 大内核锁

是一个全局自旋锁，它的目的是实现从最初的 Linux SMP 过渡到细粒度加锁机制。但是目前它已经成为内核可扩展性的障碍，所有新代码中不再使用 BLK 了。

10.9 顺序锁

seq 锁，为读写共享数据提供了一种简单机制。主要靠一个序列计数器实现。当有疑义的数据被写入，会得到一个锁，并且序列值增加。读取数据之前和之后，序列号都会被读取。

  • 如果读取的序列值相同，说明读操作没有被写操作打断过。
  • 如果读取的是偶数，说明，写操作没有发生。（因为锁的初始值是 0，写锁会让锁变成奇数，释放的时候变成偶数）

10.9.1 顺序锁的理想使用场景

  1. 数据存在很多读者
  2. 数据写者很少
  3. 写优先于读，且读者不能让写者饥饿
  4. 数据很简单，甚至是简单的整型

10.10 禁止抢占

内核是抢占性的，所以一个任务与被抢占的任务可能会在同一个临界区内运行。为了避免这种情况，内核抢占代码使用自旋锁作为非抢占区域的标记，如果一个自旋锁被持有，内核就不能进行抢占。内核抢占相关函数：

函数 描述
preempt_disable() 增加抢占计数值，从而禁止内核抢占
preempt_enable() 减少抢占计数值，并当该值降为 0 时检查和执行被挂起的需调度的任务
preempt_enable_no_resched() 激活内核抢占但不再检查任何被挂起的需调度任务
preempt_count() 返回抢占计数

10.11 顺序与屏障

10.11.1 顺序存在的意义

处理多处理器或硬件设备的同步问题时，需要以一定的顺序进行读写操作。所有可能重新排序或写的处理器提供了机器指令来确保顺序要求，这些确保顺序的指令称作屏障。

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

第 12 章 - 内存管理

12.1 页

物理页是内存管理的基本单位。大多 32 位体系结构支持 4 KB 的页，64 位支持 8 KB 的页。

  • 为什么处理器最小可寻址单位是字节，但内存管理基本单位却是页？

    因为内存管理单元 MMU 通常以页为单位进行处理。（MMU ：管理内存并将虚拟地址转化为物理地址的硬件）所以从虚拟内存的角度看，页是最小单位。

  • 页的结构体表示位于 <linux/mm_types.h> 中

  • 页会消耗多少内存？

    一 struct page 按 40 字节（根据具体结构体占位计算）算，假设系统的物理页大小为 8 KB，系统有 4 GB 物理内存，那么系统中共有页面

    而描述这么多页面的 page 结构体消耗的内存只不过 20 MB，代价不算太高。

12.2 区

页可以划分为不同的区（zone），这么划分的原因：有些页位于内存中特定的物理地址上，所以不能将其用于一些特定的任务。

12.2.2 Linux 中由于硬件缺陷而引起的内存寻址问题

  1. 某些硬件只能用特定内存地址访问 DMA（直接内存访问）
  2. 一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多。所以有一些内存不能永久映射到内核空间。

12.2.3 Linux 中主要使用的区

区 描述 物理内存
ZONE_DMA DMA 使用的页 $<16\ MB$
ZONE_NORMAL 正常可寻址的页 $16\sim896\ MB$
ZONE_HIGHMEM(所在内存时高端内存) 动态映射的页 $>896\ MB$
  • ZONE_HIGHMEM 区中的页并不能永久映射到内核地址空间

12.3 低级页分配方法

具体可以参考 <linux/gfp.h>

方法 描述
alloc_page(gfp_mask) 只分配一页，返回指向页结构的指针
alloc_pages(gfp_mask, order) 分配$2^{order}$个页，返回指向第一页页结构的指针
__get_free_page(gfp_mask) 只分配一页，返回指向其逻辑地址的指针
__get_free_pages(gfp_mask, order) 分配$2^{order}$页，返回指向第一页逻辑地址的指针
get_zeroed_page(gfp_mask) 只分配一页，让其内容填充0，返回指向其逻辑地址的指针

可以通过void free_pages(unsigned long addr, unsigned int order)等方法释放页，谨慎使用，如果传递错误addr或者order会导致系统崩溃。

12.4 gfp_mask 标志

均在 <linux/gfp.h> 中声明

  1. 行为修饰符：指定分配器行为
标志 描述
__GFP_WAIT 分配器可以睡眠
__GFP_HIGH 分配器可以访问紧急事件缓冲池
__GFP_IO 分配器可以启动磁盘I/O
__GFP_FS 分配器可以启动文件系统I/O
__GFP_COLD 分配器应该使用高速缓存中快要淘汰出去的页
__GFP_NOWARN 分配器将不打印失败警告
__GFP_REPEAT 分配器在分配失败时重复进行分配，但是这次分配还存在失败的可能
__GFP_NOFALL 分配器将无限的重复进行分配。分配不能失败
__GFP_NORETRY 分配器在分配失败时不会重新分配
__GFP_NO_GROW 由 slab 层内部使用
__GFP_COMP 添加混合页元数据，在 hugetlb 的代码内部使用
  1. 区修饰符：指定内存分配在哪个区
标志 描述
__GFP_DMA 从 ZONE_DMA 分配
__GFP_DMA32 只在 ZONE_DMA32 分配
__GFP_HIGHMEM 从 ZONE_HIGHMEM（优先） 或者 ZONE_NORMAL 分配
  1. 类型标志：指定行为和区描述符
标志 关联的修饰符 描述
GFP_ATOMIC __GFP_HIGH 这个标志用在中断处理程序、下半部、持有自旋锁以及其他不能睡眠的地方
GFP_NOWAIT 0 与 GFP_ATOMIC 类似，不同之处在于，调用不会退给紧急内存池。 这就增加了内存分配失败的可能性。
GFP_NOIO __GFP_WAIT 这种分配可以阻塞，但不会启动磁盘I/O。 这个标志在不能引发更多磁盘I/O时能阻塞I/O代码，可能导致递归
GFP_NOFS __GFP_WAIT或__GFP_IO 这种分配在必要时可能阻塞，也可能启动磁盘I/O，但不会启动文件系统操作。 这个标志在你不能再启动另一个文件系统的操作时，用在文件系统部分的代码中
GFP_KERNEL (__GFP_WAIT ｜ __GFP_IO ｜ __GFP_FS ) 这是常规的分配方式，可能会阻塞。这个标志在睡眠安全时用在进程上下文代码中。 为了获得调用者所需的内存，内核会尽力而为。这个标志应当是首选标志
GFP_USER (__GFP_WAIT ｜ __GFP_IO ｜ __GFP_FS ) 这是常规的分配方式，可能会阻塞。这个标志用于为用户空间进程分配内存时
GFP_HIGHUSER (__GFP_WAIT ｜ __GFP_IO ｜ __GFP_FS )｜__GFP_HIGHMEM) 从 ZONE_HIGHMEM 进行分配，可能会阻塞。用于为用户空间进程分配内存
GFP_DMA __GFP_DMA 从 ZONE_DMA 进行分配。需要获取能供 DMA 使用的内存的设备驱动程序使用这个标志。通常与以上的某个标志组合在一起使用。

12.4.1 什么时候用什么标志？

情形 标志
进程上下文，可以睡眠 使用 GFP_KERNEL
进程上下文，不可以睡眠 使用 GFP_ATOMIC，在睡眠之前或之后以 GFP_KERNEL 执行内存分配
中断处理程序/软中断/tasklet 使用 GFP_ATOMIC
需要用于DMA的内存，可以睡眠 使用 (GFP_DMA｜GFP_KERNEL)
需要用于DMA的内存，不可以睡眠 使用 (GFP_DMA｜GFP_ATOMIC)，或者在睡眠之前执行内存分配

12.5 malloc、kmalloc、vmalloc 区别

  1. malloc 返回的页在进程的虚拟地址空间是连续的，但物理空间不一定是连续的
  2. kmalloc 确保物理地址也是连续的（虚拟地址自然也是连续的）
  3. vmalloc 只确保页在虚拟地址空间是连续的

出于性能考虑，很多内核代码使用 kmalloc 获取内存。因为 vmalloc 为了把物理地址空间不连续的页转换为虚拟地址空间连续的页，会专门建立页表项，并一个一个进行映射，这会导致比直接内存映射有更大的 TLB 抖动。

12.6 slab 层

TLB

TLB（Translation lookaside buffer）是一种硬件缓冲区，用于缓存虚拟地址到物理地址的映射关系，可以极大提高系统性能。

第 13 章 - 虚拟文件系统

第 14 章 - 块 I/O 层

第 15 章 - 进程地址空间

第 16 章 - 页高速缓存和页回写

第 17 章 - 设备与模块

第 18 章 - 调试

第 19 章 - 可移植性

第 20 章 - 补丁、开发和社区



----------- 本文结束 -----------




0%