Linux Kernel Development 学习与总结

引言

最近抽时间把 Operating Systems: Three Easy Pieces 终于看完了（其实 2017 年就知道它了，没想到拖到了 2019 年 😅），全书分三个部分（虚拟化、并发、持久化）对操作系统的一些通用设计思想进行了介绍，学完后，对于进程、内存虚拟化、并发、文件系统有了更加深刻的认识。但是，真实的世界是什么样子的呢？这就是希望在阅读《Linux 设计与实现》（Linux Kernel Development）后找到想要的答案。当然，在学习中也针对很多部分搜集了不少学习资料，整理在文后，方便加深理解。

在学习之前，思考了一些问题，可以在学习中探索这些问题的答案：

1. Linux 中进程、线程是如何实现的？各种调度策略是什么样的？又是怎么实现的呢？
2. 并发问题肯定需要注意，Linux 中如何应对竞态条件 & 数据竞争呢？各种常见的同步原语又是如何实现的？
3. Linux 的内存虚拟化是如何实现的？内存布局？虚拟地址空间？
4. 文件系统有很多，操作系统是怎么进行抽象，并对用户提供一致优雅的系统调用接口的呢？
5. Linux 内核中有哪些非常经典的算法和数据结构的应用？它们使用场景是什么？怎么实现的呢？

Linux 内核简介

说到 Linux，就不得不提到它的祖先 Unix 系统。Unix 在 1970 年左右被 Ken Thompson 首先在一台 PDP-7 机型上实现，而后移植到 PDP-11 机器上，1973 年它被使用 C 语言重写，提供了更加强大的可移植性。

经过多年发展，Unix 系统成为了一个强大、健壮且稳定的操作系统。其强大的根本原因如下：

1. 简洁，仅提供数百个设计目标明确的系统调用；
2. 所有的东西都被当作文件看待
3. 很强的移植能力
4. 进程创建非常迅速，拥有独特的 fork() 系统调用
5. 拥有简单且稳定的进程间通信原语

Linux 是类 Unix 系统，它的实现和 Unix 也有一些大相径庭的方面，但是它依然继承了 Unix 的设计目标，保证了 API 的一致性（有品位的程序员都应该要学习这一思想）。

Linux 词汇一般用来指代内核。它的基础包括：

1. 内核
2. C 库
3. 工具集
4. 系统的基本工具，如 Shell

什么是操作系统？宽泛的操作系统是指整个系统中负责完成最基本功能和系统管理的部分，包括内核、设备驱动、启动引导程序、命令行 Shell 或用户界面、文件管理工具和系统工具。内核则是那个最亮的仔，它通常由如下几个重要部分组成：

1. 中断服务
2. 任务调度程序
3. 内存管理程序
4. 网络
5. 进程间通信等系统服务

Linux 的中断服务是不在进程上下文执行的，而是在一个与所有进程无关、专门的中断上下文执行。这样可以保证第一时间能够响应和处理中断请求，然后快速退出。

处理器在任意时间点活动可概括为以下三种之一：

1. 运行在用户空间，执行用户进程
2. 运行在内核空间，处于进程上下文，代表某个特定的进程执行（如某个系统调用）
3. 运行在内核空间，处于中断上下文，与进程无关，处理特定的中断

微内核和宏内核

这个是比较有趣的历史了，操作系统设计有两大主要阵营：微内核和宏内核。

微内核的功能划分成多个独立的过程，每个过程都是一个服务（C/S 模型，服务与内核交互）。系统采用 IPC 禁止互通消息，互换「服务」。服务的独立性可以避免一个服务失败殃及其它服务。模块化设计也非常适合热插拔。但是缺点就是 IPC 的开销多于函数调用（类比微服务的网络开销和在本地调用函数的开销）。

宏内核则是实用主义者喜欢的设计，它是比较简单的设计，整体上就是一个单独的过程，运行在一个单独的地址空间。内核之间的通信微不足道，性能高。

Linux 自然是宏内核设计，Linux 内核运行在单独的内核地址空间上。同时它也采纳了微内核的精华，使它成为模块化的、多线程的以及内核本身可调度的操作系统。

与传统 Unix 区别

1. 支持动态加载内核模块（这个不是微内核宣称的好处吗？咱也有）
2. 支持对称多处理机制（SMP）
3. 内核可以抢占（preemptive）：任务可以有优先级
4. 对多线程的支持很特别：内核不区分线程和一般的进程，对于内核而言，所有的进程都一样，只是其中的一些共享资源而已
5. 具有设备类的面向对象的设备模型、热插拔事件，用户空间的设备文件系统（sysfs）
6. 忽略了一些拙劣特性
7. 自由：任何改变都必须要能通过简洁的设计及正确可靠的实现来解决现实中确实存在的问题

内核版本

<主版本>.<从版本>.<修订>[.<稳定版本号>]，其中从版本号为偶数，则为稳定版本，否则为开发版本。

内核编译

配置

可以使用的配置方式如下：

1. make config
2. make menuconfig1
3. make gconfig
4. 默认配置：make defconfig

验证和更新配置：make oldconfig

编译

1. 直接编译：make
2. 导出不关心的 info：make >/dev/null
3. 指定并行编译数量：make -j4 >/dev/null

内核开发特点

1. 不能使用标准 C 库

2. 必须使用 GNU C（需要用到它的一些扩展特性）

   1. inline：通常将对时间要求比较高，函数本身比较短的定义成内联函数。在内核中，为了类型安全和易读性，优先使用 inline 函数，而非复杂的宏
   2. 内联编译：支持使用 asm() 嵌入汇编代码
   3. 分支声明：可以使用 likely() 和 unlikely() 声明分支是否经常出现或很少出现，指导编译器进行优化（要搞清楚，否则优化反而变成了拖累）

3. 缺乏像用户空间中的内存保护机制

   1. 内核中发生内存错误会导致 oops，内核可能会死掉
   2. 内核中的内存是不分页的，每用掉一个字节，物理内存就减少一个字节

4. 难以执行浮点数计算

   1. 不能像用户空间执行浮点数计算那样，可以通过 trap 的方式将整数模式转换到浮点数模式计算
   2. 内核不能完美支持浮点数计算，本身也无法陷入。非要执行的话，就需要手动保存和恢复浮点寄存器，非常麻烦

5. 内核给每个进程只有一个很小的定长堆栈

   1. 用户空间的栈可以动态增长，可支持非常大的数据结构
   2. 内核栈的大小和体系结构有关（如 x86 可以是 4KB/8KB）
   3. 历史上来说，内核栈大小是两页，32 位是 8KB，64 位是 16KB；每个处理器都有自己的栈

6. 由于要支持异步中断、抢占和 SMP，时刻需要注意并发安全和同步

7. 考虑可移植性
   1. 保持字节序
   2. 64 位对齐
   3. 不假定字长和页面长度

进程

管理进程

1. 内核把进程的列表存放在 task list 双向链表中，每个 entry 的类型是 task_struct，被称为 process descriptor
2. 通过 slab（更新的应该是 SLUB） 分配器分配 task_struct 结构体（对象复用和缓存着色），每个任务的 thread_info 位于内核栈的尾端，其中包含指向 task_struct 的指针及其它信息
3. 进程通过 PID 进行区分，其值存放在 process descriptor 中。由于进程处理代码需要频繁访问 task_struct 信息，所以在 PowerPC 等机器上，有专门的寄存器存储了相应的指针；而在 x86 体系下，则是利用内核栈尾创建的 thread_info，并借助偏移计算间接查找 task_struct 结构体

4. 进程状态：

   1. TASK_RUNNING
   2. TASK_INTERRUPTABLE
   3. TASK_UNINTERRUPTABLE
   4. __TASK_TRACED: 被其它进程跟踪的进程（如 ptrace 对调试程序进行跟踪）

   5. __TASK_STOPPED: 进程停止执行，没有投入运行也无法投入运行

      

5. 所有的进程都是 PID 为 1 的 init 进程的后代，init 进程的描述符是作为 init_task 静态分配的（比较特殊）

6. Unix 系统进程创建：

   1. 通过 fork() 拷贝当前进程创建一个子进程（区别父进程：有新的 PID，有某些资源和统计量）
   2. exec() 函数负责读取可执行文件并将其载入地址空间开始运行

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

8. Linux 中的 fork() 和 vfork() 都是通过 clone() 系统调用实现的。vfork() 的特点是：不拷贝父进程的页表，且子进程作为父进程的单独线程在它的地址空间执行，父进程阻塞直到子进程退出或执行 exec()

9. Linux 中的线程实现：

   1. 从内核角度看，没有线程的概念，所有的线程都当作进程看待，只是与其它进程共享某些资源。每个线程都拥有属于自己的 task_struct
   2. 其它系统中，线程被抽象成一种耗费资源较少的资源，运行迅速的执行单元
   3. 通过 clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0); 创建线程
   4. 对比 fork() 实现：clone(SIGCHLD, 0)
   5. 对比 vfork() 实现：clone(CLONE_VFORK | CLONE_VM | SIGCHLD, 0)

10. 内核线程：

    1. 内核通常需要在后台执行一些操作，这些任务可通过 kernel thread 完成。这种是运行在内核空间的标准进程
    2. 内核线程没有独立的地址空间，可被调度，可被抢占

11. 进程终结：

    1. 通常通过 do_exit() 完成退出，期间会释放相关的资源，最终将进程状态设置为 EXIT_ZOMBIE，但是此时的内核栈、thread_info 和 task_struct 结构体还是存在的，从而给父进程提供信息
    2. 父进程获得已终结的子进程信息后（父进程可通过 wait() 系统调用收集信息），或者通知内核它不关注这些信息，才会释放剩余的内存空间

12. 孤儿进程：

    1. 退出时永远处于僵死状态，白白浪费内存
    2. 解决办法就是在当前线程组寻找某个线程作为父亲，实在不行，就让 init 接盘

调度进程

1. 多任务系统分为两类：

   1. 非抢占式多任务（cooperative multitasking）
   2. 抢占式多任务（preemptive multitasking）

2. 进程调度策略会关心进程的优先级、时间片

3. Linux 中的进程分为普通进程和实时进程，其中前者的优先级在 (-20, +19），而后者则是 (0, 99)。此外，实时进程的优先级总是高于普通进程优先级的，所以普通进程的优先级映射过来就是 (100, 139)
4. Linux 中可以通过 nice 调整进程的优先级，越小的值拥有越高的权重；反之，则权重越低（体现在时间片上）

CFS 调度器

1. Linux 2.6 内核引入了 CFS 调度器（位于 sched/fair.c）作为普通进程的调度器，它是一个近乎完美的公平调度器（权衡周转时间和响应时间）。并非采用时间片进行分配，而是给进程分配了处理器使用的比重，从而确保进程调度中能够有恒定的公平性，从而将切换频率置于不断变动中
2. CFS 基于一个简单的理念：进程调度的效果应该等同于系统拥有一个完美的多任务处理器，每个进程都能获得 1/n_running 处理器时间
3. CFS 允许每个进程运行一段时间，循环轮转，总是选择 vruntime 最小的进程作为下一个执行。也就是说，是通过所有可运行经常总数为基础来计算出进程应该运行多久，而非依靠 nice 值来计算时间片（传统的做法就是这种）
4. 调度器实现概要：
   1. sched_entity 结构体跟踪运行记账（其中包含 vruntime）
   2. 所有可运行的进程都位于一棵黑红树中（O(logN) 时间复杂度查找），并且每次都会从树的最左叶子节点上（leftmost）找到 vruntime 最小的那个进程运行（实时上，这个值是提前缓存好的）
   3. 调度器入口处会找到最高优先级的调度类，然后获取到谁是下一个该运行的进程
   4. 睡眠：进程会把自己标记成休眠状态，从可执行红黑树中溢出，并放入等待队列，调用 schedule() 执行一个其他进程
   5. 唤醒：进程被设置为可执行状态，从等待队列移除，添加到可执行红黑树
5. CFS 实现了如下几种调度策略：
   1. SCHED_NORMAL（以前叫做 SCHED_OTHER）：用于普通任务调度
   2. SCHED_BATCH：并非像普通任务那样被频繁抢占，会尽可能允许任务运行足够长时间，从而利用上 CPU 亲和性以及更好地复用缓存
   3. SCHED_IDLE：这种任务优先级比 nice 19 还要低

抢占

1. 用户抢占（检查 need_resched 标识符）：从系统调用返回用户空间时；从中断处理返回用户空间时
2. 内核抢占（thread_info 中存在 preemt_count 计数器，表示有没有锁被持有）：就是调度程序能够在内核任务执行期间被执行
   1. 只要重新调度是安全的（没有持有锁），内核就可以在任何时间抢占正在执行的任务
   2. 内核抢占时机：
      1. 中断处理程序正在执行，且返回内核空间之前
      2. 内核代码再次具有可抢占性时
      3. 内核任务显式调用 schedule()
      4. 内核中的任务阻塞（此时会导致调用 schedule()）

实时调度器

1. 实时调度器是在 sched/rt.c 中实现的，它使用了 100 个运行队列（对应 1~99 任务优先级），实现了 SCHED_FIFO 和 SCHED_RR 策略。

2. SCHED_FIFO:

   1. 简单的先入先出调度算法，不依赖时间片
   2. 该级别任务比 SCHED_NORMAL 级别的进程先得到调度
   3. 一旦任务处于执行期间，就会一直执行下去；只有更高优先级的 SCHED_FIFO/SCHED_RR 任务才可以抢占

3. SCHED_RR:

   1. 类似 FIFO，但是每个任务会有分配的时间片，时间片耗尽后就要换其它任务执行
   2. 对于 FIFO 进程，高优先级始终抢占低优先级进程；低优先级进程不能抢占 SCHED_RR 进程，即便其耗尽了时间片

4. Linux 提供的是软实时工作方式，尽力使得进程能够在限定的时间到来前执行，但内核不保证总能满足这些进程的要求

调度器类

调度器类需要实现一些 hooks，这样可以在需要的时候做合适的操作。部分 hooks 如下：

• enqueue_task
• dequeue_task
• yield_task
• check_preempt_cur
• pick_next_task
• set_curr_task
• task_tick

调度相关的 syscall

系统调用	描述
nice()	设置进程的 nice 值
sched_setscheduler()	设置调度策略
sched_getscheduler()	获取调度策略
sched_setparam()	设置实时优先级
sched_getparam()
sched_rr_get_interval()	时间片值
sched_setaffinity()	设置处理器亲和力
sched_getaffinity()	获取进程处理器亲和力
shced_yield()	暂时让出处理器

系统调用

众所周知，进程是在操作系统提供的用户空间运行的，而如果需要打开文件等操作，需要通过系统调用，陷入到内核态，由操作系统代替完成和硬件的交互，从而为进程提供服务。所以说，系统调用时在用户空间和进程和硬件设备之间的一个中间层。这个中间层的主要作用如下：

1. 为用户空间提供硬件接口抽象
2. 系统调用保证系统的安全和稳定
3. 操作系统可以掌控进程的硬件访问意图，并且代劳

那么系统调用又是如何实现的呢？一句话总结为：当系统调用执行时，会陷入到内核，传递系统调用号和参数，执行正确的系统调用函数，并且把返回值带回用户空间。可见，系统调用非常特殊，完全不同于常规的函数调用，看起来非常 Hack。

接下来，通过几个问题，加深对上述描述的理解：

1. 如何陷入到内核？通过软中断的方式实现，通过引发一个异常触发系统切换到内核态执行异常处理程序。
2. 什么是系统调用号？在 Linux 中，每个系统调用都被赋予了一个编号，进程其实是通过系统调用号而不是名称来告知内核自己中意哪个系统调用的。
3. 如何传递系统调用号？通过寄存器传递，在 x86 中，就是将系统调用号放在 eax 寄存器传递给内核的。
4. 参数是如何传递的？
   1. 第一种方式就是将参数放在寄存器中，一般来说系统调用参数不会很多。在 x86 中，可以用 ebx, ecx, edx, esi 和 edi 按顺序存放五个参数。
   2. 第二种方式就是将参数存放在用户空间内存中，并将参数指针存放在寄存器中。这种是为了应付参数超过 6 个情况。
5. 返回值如何带给用户空间？当然也是通过寄存器来传递的，在 x86 中，可以使用 eax 寄存器。

内核数据结构

Linux 内核链表实现独树一帜。它是将链表塞入到数据结构，而非常规的那种在数据结构中塞入链表。

可以看下对比就知道为何特别了：

// 常规定义方法
struct node {
    void *data;
    struct node *prev;
    struct node *next;
}

// Linux 内核链表定义
struct list_head {
    struct list_head *prev;
    struct list_head *next;
}

struct node {
    void *data;
    struct list_head list; // 所有的 node 形成链表
}

这样，通用的链表操作就可以基于 struct list_head 来实现了。那如何和根据链表指针获得对应的 node 呢？答案是通过 container_of() 宏，实际上 C 语言中，一个给定结构体中的变量偏移在编译时就已经确定了，所以可以借此获得父结构中的任意变量：

#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type, member) );})

中断和中断处理

中断是各种硬件设备与处理器协同高效工作的方式之一。处理器执行指令的速度非常快，而一些外部设备则会慢很多；为了能够保证 CPU 不浪费时间轮询设备状态，而降低利用率，所以需要中断机制来通知 CPU。当处理器接收到中断后，会去执行已注册的相关中断处理程序。

需要注意的是，中断和前面提到的异常（Fault）是不同的：

1. 中断通常是异步发生的，不考虑时钟同步；
2. 异常则必须与处理器时钟同步，所以也被称为同步中断（如除 0 错误、缺页）。

Linux 中对于中断的响应和处理分成上半部和下半部。其中上半部会在接收到中断信号后快速完成必要工作的（有严格的时限），而更加繁重的任务则会在下半部执行。在上半部需要快速执行，且无法睡眠；但下半部则没有这样的限制。

无须重入

Linux 中的中断处理不用考虑重入，因为当给定中断处理程序在执行时，对应中断线在所有处理器上被屏蔽，避免同一中断线接收另外的中断。这样做简化了中断处理程序的编写。

中断上下文

所谓的中断上下文（interrupt context），就是在执行中断处理程序时，内核所处的上下文。中断上下文和进程上下文没有半毛钱关系，我们可以把它和进程上下文进行一番对比：

中断上下文	进程上下文
执行中断处理程序时，内核所处的上下文	内核代表进程执行（系统调用、运行内核线程）时，所处的操作模式
与进程无瓜，与 current 宏无瓜	可通过 current 宏关联当前进程
没有后备进程，无法睡眠，也不能调用会导致睡眠的函数	可睡眠，可调用调度程序
有严格的执行时限	没有非常严格的要求

下半部及推后执行的工作

下半部就是执行和中断处理相关，但是中断处理程序中不会执行的工作。引入下半部的目的就是让中断处理程序尽可能地简短、快速，避免屏蔽中断太久，导致系统的响应能力和性能受到影响；而比较繁重的工作可以在下半部执行。

下半部主要实现方式：

1. 软中断
   1. 对于时间要求严格，且能自己高效完成加锁的工作，可使用软中断（如网络、SCSI）
   2. 软中断执行期间，允许响应中断，但它自身不能睡眠
2. tasklet
   1. 基于软中断实现，同一个处理程序的多个实例不能再多个处理器同时运行
   2. 用途广泛，接口简单，性能不错
   3. 不能睡眠
3. 工作队列中的工作可以交给内核线程推后执行（会在进程上下文执行），可以利用进程上下文的优势，且可以重新调度和睡眠

内核同步

在进行内核编程时，时刻需要注意并发带来的问题，需要能够正确识别临界区，正确加锁、解锁，保证关键数据结构不被错误修改。那么有哪些情况能造成并发问题呢？

1. 中断：异步发生，会中断当前正在执行的代码
2. 软中断和 tasklet：内核会在任意时刻唤醒软中断和 tasklet，打断当前正在执行的代码
3. 内核抢占：内核中的任务可能被其它任务抢占
4. 睡眠及与用户空间同步：在内核中执行的进程可能会睡眠，从而导致调度程序被唤醒，并运行新的用户进程
5. SMP：多个处理器会并行执行

定时器和时间管理

内核需要在硬件（RTC 和 Timer）的帮助下才能计算和管理时间，内核通过已知的（这个时钟周期是可编程的，可确定的）时钟中断间隔来计算 wall time 和 jiffies（系统启动以来的节拍总数）。那么，在时钟中断发生时究竟会做哪些工作呢？以下给出一些会周期执行的工作：

1. 更新系统运行时间和实际时间
2. 对于 SMP 系统，需要均衡各处理器上的任务队列，如果运行队列负载不均衡，需要尽量让它们均衡
3. 检查当前进程是否用尽了自己的时间片，如果时，则重新进行调度
4. 运行超时的动态定时器
5. 更新资源消耗和处理器时间统计值

内存管理

页

内核是把物理内存分页管理的，也就是说页（page）是最基本的管理单元。MMU 也是以页大小为单位转换虚拟地址到硬件地址的。不同的体系结构，页大小不同，一般 32 位系统是 4KB，64 位系统是 8KB。

区

因为硬件存在限制，内核无法对所有的页一视同仁。因此需要把页划分成不同的区（zone），内核需要处理如下因为硬件缺陷而引起的内存寻址问题：

1. 一些硬件只能用特定的内存地址执行 DMA 操作
2. 一些体系结构的内存物理寻址范围比虚拟地址范围大

内核的分区有四种：

1. ZONE_DMA：可执行 DMA 操作的页集合
2. ZONE_DMA32：同上，但仅限于 32 位设备
3. ZONE_NORMAL：能够正常映射的页
4. ZONE_HIGHMEM：高端内存区域，其中的页不能永久映射到内核地址空间（这里限于 32 位地址空间，64 位就不会有问题了）

页申请和释放

1. alloc_page(gfp_mask)：只分配一页，返回指向页结构的指针
2. alloc_pages(gfp_mask, order)：分配 2^order 个连续页
3. __get_free_page(gfp_mask)：只分配一页，返回指向其逻辑地址的指针
4. __get_free_pages(gfp_mask, order)：分配 2^order 个连续物理页，返回逻辑地址指针
5. get_zeroed_page(gfp_mask)：只分配一页，且填充 0 ，返回逻辑地址指针
6. __free_pages(struct page *page, unsinged int order)
7. free_pages(unsigned long addr, unsinged int order)
8. free_page(unsigned long addr)

kmalloc

void *kmalloc(size_t size, gfp_t flags)，kmalloc() 类似于 malloc()，可以获得指定字节大小的内核内存，它分配得到的页的物理地址是连续的，所以虚拟地址也是连续的。
void kfree(const void *ptr) 释放分配的内存空间

关于标记位，常用的是 GFP_KERNEL，允许睡眠，用于进程上下文空间；另外的 GFP_ATOMIC，则不可以睡眠，可用于进程上下文、中断处理程序、软中断、tasklet。

vmalloc

vmalloc() 类似 kmalloc()，不同的是，它分配的内存虚拟地址虽然是连续的，但是实际的物理地址无需连续。它通过分配非连续的物理内存，再「修正」页表，从而把内存映射到逻辑地址空间连续的区域。它需要专门的页表来完成连续虚拟地址到实际非连续物理地址的映射，开销较大，且容易引起 TLB 抖动，通常在内核中更倾向于使用 kmalloc()。

slab 层

slab 层充当通用数据结构的缓存层的角色，它会为不同的对象划分成不同的高速缓存组，每组存放不同类型的对象。比如，存放 task_struct 和 inode 就分属于不同的组。kmalloc() 也是基于 slab 层之上，使用了一组通用高速缓存。

slab 分配器引入的目的：

1. 避免频繁使用的对象需要频繁分配和释放，降低开销
2. 频繁分配回收容易导致内存碎片，减少碎片问题
3. 提高性能
4. 部分缓存专属于某个处理器时，可以实现无锁分配和释放（tcmalloc）

虚拟文件系统（VFS）

VFS 是 Linux 提供的一个文件系统抽象层，涵盖了任何文件系统的常用功能集和行为，从而支持各种实际的文件系统（如 NTFS, FAT, EXT4）。

用户空间 write() -> VFS sys_write() -> 文件系统的写方法 -> 存储设备

Unix 文件系统传统抽象概念：File, DirectoryEntry, Index Node 和 Mount Point。Unix 文件的特点是面向字节流抽象设计的，具有简单、灵活的特性。在 Unix 中，目录也是普通文件，其列出了包含在目录中所有文件。

VFS 中的主要对象：

1. 超级块对象，代表具体已安装的文件系统
2. 索引节点对象，代表一个具体的文件
3. 目录项对象，代表一个目录项，是路径的组成部分
4. 文件对象，代表由进程打开的文件（其实它会指向目录项对象，而目录项对象才是真正表示已打开的实际文件，因为其中包含了指向 inode 的指针）

块 I/O

Linux 中，设备分为三类：

1. 块设备：支持随机访问固定大小的数据块，如硬盘、闪存
2. 字符设备：以字符流的形式被访问，如键盘
3. 网络设备

需要注意的是，针对块设备的请求会被操作系统挂起在 I/O 请求队列上，并且由 I/O 调度程序来管理请求队列。它会决定请求队列中的请求如何排序，以及何时发送到具体的块设备。之所以这么做，就是期望借助 I/O 调度程序，对请求进行合并和排序，从而有效提高系统的整体性能（也可能造成某些请求得不到公平对待，甚至出现饥饿的情况）。以下记录的是 Linux 中已经实现的几种 I/O 调度算法：

1. Linus 电梯

   1. 支持向前和向后合并（通常都是这种居多）
   2. 有较好的全局吞吐量
   3. 会发生请求饥饿问题

2. 最终期限（deadline） I/O 调度

   1. 降低了系统的全局吞吐量
   2. 读请求超时 500ms，写请求超时 5s，超时必然得到服务，避免长时间饥饿的问题

3. 预测（anticipatory） I/O 调度

   1. 目标是保持较好的读响应同时，提供良好的全局吞吐量。视图减少在进行 I/O 操作期间，处理新到的读请求带来的寻址数量
   2. 请求提交后不会直接返回处理其它请求，而会空闲片刻（几毫秒），等待应用提交其它读请求

4. 完全公平排队 I/O 调度（CFQ）

   1. 为特殊工作负载的场景设计，每个进程都有自己的请求队列
   2. 以时间片轮转调度队列，处理队列中的请求

进程地址空间

现代操作系统通过采用虚拟内存技术，为每个进程提供了独立的地址空间，从而给每个进程营造了独享内存的假象，这是内存虚拟化的重要机制。需要注意的是，现代采用虚拟内存的系统通常都使用平坦地址空间，而非分段式的内存模式。

值得注意的是，内存地址空间会根据需要划分成不同的区域。内核可以给进程地址空间动态添加或减少内存区域。每个进程只能访问有效内存区域内的内存地址，每个内存区域会包含权限等属性。进程中任意有效地址只能位于唯一的区域，且这些区域不能相互覆盖。

内存区域可以包含各种内存对象：

1. 可执行文件代码的内存映射，text section
2. 可执行文件已初始化全局变量的内存映射，data section
3. 包含未初始化的全局变量，BSS 段的零页的内存映射
4. 进程用户空间栈的零页内存映射
5. 每个一个诸如 C 库或动态连接程序等共享的 text section, data section 和 bss 也被载入到进程地址空间
6. 内存映射文件
7. 共享内存段
8. 匿名映射，如 malloc() 分配的内存

mm_struct -> vm_area_struct

64 位系统进程地址空间布局

每一个进程都有 64bit 的地址空间，其中用户空间可以使用一半的地址空间（128 TiB），而另一半则是内核空间使用。内核通常驻留在内存中，并且会被映射到每个进程的虚拟内存当中。而在内核中，所有的内核线程都共享一个地址空间。详细的内存布局可以参考后面的学习资料~

页表

Linux 中使用三级页表完成地址转换，使用多级页表可以节约地址转换需要占用的空间。但由于完成虚拟页地址到物理页地址转换都需要在三级页表中查找到映射，开销比较高。所以很多体系结构提供了 TLB 作为地址映射的硬件缓存。

总结

总体上来说，这本书还是比较适合对操作系统基本概念有一定了解，且对于 Linux 内核也有一点了解的前提下阅读，否则在看到一些概念的时候会比较吃力。比如对于进程、线程的抽象定义，虚拟内存中讲到的分页、分段概念以及多级页表的概念。另外，对于常用数据结构需要有清晰的认识；并发相关的同步问题也有了解。
虽然整本书是基于 Linux 2.6.3x 内核为基础的，如今的 Linux 内核已经发展到 5.x 时代了，这期间变化肯定有很多。但这本书的价值还是存在的，其中讲得很多思想、方法依然实用，可以变通地去看待和理解。

名词解释

1. POSIX: Portable Operating System Interface
2. TLB: Translation Lookup Buffer
3. CFS: Complete Fair Scheduler
4. CFQ: Complete Fair Queueing，这个是 IO 调度器之一
5. VFS: Virtual File System
6. VMA: Virtual Memory Area
7. MMU: Memory Map Unit
8. jiffies: Linux 中用来记录系统启动以来的节拍数的全局变量，还有一个 jiffies_64
9. ISR: Interrupt Service Routine

深入学习

• 《Linux 内核设计与实现 Linux Kernel Development，第 3 版》
• Are Threads Implemented As Processes on Linux
• POSIX 线程
• Linux 线程实现
• Linux Sched Doc CFS
• A complete guide to Linux process scheduling
• Linux Memory
• Linux memory management
• x86_64 内存映射
• The Memory Layout of a 64-bit Linux Process
• Linux kernel memory layout
• Chapter 3 Page Table Management
• Linux 调度器资料整理
• Linux Kernel Map
• Entering God Mode — The Kernel Space Mirroring Attack