Linux 内核设计与实现读书笔记
单内核和微内核设计
单内核：单模块二进制文件，直接通信，一个大内核地址空间，单独的大过程 微内核：过程被划分成多个独立的过程，每个过程叫做一个服务器，有强烈请求特权服务的服务器才运行在特权模式下，其他服务器都运行在用户空间。使用消息传递的方式处理微内核的通信，各个服务器（进程）通过IPC的方式互通消息。但传递消息会产生额外的开销
linux 属于单内核，并且让内核的所有事情都运行在内核态，直接调用而不是传递消息，支持动态加载或者卸载部分内核代码，内核并不区分县城和进程，只不过其中一些共享资源而已
内核活动范围
- 运行于用户空间，执行用户进程
- 运行于内核空间，处于进程的内核空间中，代表某个特定的进程执行
- 运行于内核空间，处于中断上下文的特定空间中，与任何进程无关，处理某个特定的中断
内核开发的注意事项
- 缺乏像用户空间那样的内存保护机制
- 难以执行浮点运算（用户空间进行浮点运算的时候需要进行陷入并转换运算模式，但是在内核中只能进行手工转换模式）
- 内核栈空间大小是两页，32位下是8KB，64位下是16KB
- linux的内核是可以被抢占的
进程
进程描述符 task_struct 被存放在一个任务队列（双向循环链表）中，这个进程描述符包含打开文件，地址空间，挂起信号，进程状态。2.6起使用 slab 分配器动态分配 task_struct ，内核栈底存放着描述符的指针 访问进程描述符在X86下需要通过偏移量计算来得到描述符指针
进程上下文
执行系统调用或者触发异常的时候，就会陷入内核空间，这时内核代表进程执行并处于进程上下文（内核空间）中
进程树
所有进程都是 PID 为 1 的 init 进程的后代，每一个进程的进程描述符结构中分别保存着父进程 task 的指针和子进程的指针链表
fork()
创建使用写时拷贝技术，只有写入的时候才复制页表，如果马上就 exec() 的话就可以避免拷贝从而提高速度
vfork 有其历史原因，跟现在的写时拷贝 fork 差不多
进程终结
释放系统资源（文件引用计数减1，地址空间释放，退出返回值交给内核以供父进程检索），向父进程发信号，给子进程重新找养父，养父为线程组中其他线程或 init 进程。这时处于僵尸态：剩下 内核栈，thread_info，和task_struct。进程描述符依然被保留下来，需要父进程接收到之后才能释放
孤儿进程
优先在同一线程组中找父亲，如果不行，再让 init 做父亲
线程
从内核的视角来看，线程仅被视为一个与其他进程共享某些资源的进程 线程的创建与进程的创建的本质都是调用 clone ，只不过指定了一些共享的资源 因此 getpid 的时候进程的PID显示的是线程组的TGID！！
内核线程
与普通线程的区别：没有自己独立的地址空间，通过 kthreadd 衍生出来
进程调度策略
进程可以被分为 IO型和 CPU型，多数 GUI 都是IO型 调度策略的设计需要在进程响应时间和最大系统利用率上进行平衡
优先级：通过nice值来衡量 nice 越大，优先级更低，降低处理器使用比 越低，优先级更高，有更多的处理器使用比
2.5：O(1) 调度策略
2.6：完全公平调度算法 CFS 抢占时机由新的可执行程序消耗的处理器使用比来决定，使用比比当前运行的进程小，则新进程抢占当前进程 使用比越小的进程我们越能够确定此时它是 IO 型进程，因此对响应时间要求更高，需要在需要立即响应的时候能够抢占当前进程
使用 nice 值的相对值来确定处理器的使用比，如果进程数非常多，默认分配到的最低 CPU 时间为 1ms
每一个进程都要记录它的剩余时间片，每个系统节拍发生的时候减一，减少到 0 的时候，就会被另一个尚未减小到 0 的进程抢占
vruntime 存放进程的虚拟运行时间，这个值记录了一个程序运行了多长时间以及还应该运行多久，由系统定时器定期更新
可运行进程队列是一个红黑树，CFS利用其来迅速找到最小 vruntime 的进程来执行，最左节点会被事先缓存下来 进程添加：进程变为可运行状态或通过 fork 第一次创建进程时 进程删除：进程阻塞（变为不可运行）或者终止时 调度选择：从最高优先级调度类选择最高优先级的进程
休眠的进程会被放在一个等待队列中（简单链表实现），进程被某个条件完成唤醒之后会再次检查是否满足条件，满足：退出循环，不满足：再次调用 schedule 并重复。 例如在IO数据到来的时候，VFS要负责调用wake_up进行唤醒
用户抢占
- 发生在从系统调用返回的时候
- 发生在中断处理返回用户空间的时候
内核抢占
只要内核没有持有锁，那么内核就可以被安全抢占，进行重新调度，让出 cpu
实时调度
CFS 讨论的范围都局限于 SCHED_NORMAL 级的进程，如果有特殊的需求，可以设定为 SCHED_FIFO 和 SCHED_RR，RR相当于是带时间片的 FIFO，时间片耗尽后就不能继续执行下去，FIFO级进程处于可执行状态就可以移植后自行下去直到阻塞或显式让出CPU
系统调用
作用：
- 硬件的抽象接口
- 保证系统的稳定和安全
是用户空间访问内核的唯一手段 除异常和陷入外，它们是内核的唯一合法入口
unix接口设计：提供机制而不是策略 内核空间使用 64 位的 long 类型作为返回值表示成功或失败（为了与64位保持兼容），用户空间是int。错误的时候C库会把错误码写入errno全局变量，通过 perror() 函数可以拿到错误字符串
系统调用的实现：前面会使用 asmlinkage 关键词来确保编译器仅从栈中提取参数 系统调用通知内核的机制：通过软中断 int $0x80 触发
系统调用号 — eax 参数 — 五个寄存器 ebx, ecx,edx,esi,edi 超过五个会用单独的寄存器存储指向参数的用户空间地址指针 返回值 — eax
在进程上下文中，内核可以休眠（例如在系统调用阻塞或者显示调用schedule的时候）并且可以被抢占 因为当前进程可能会被其他进程抢占，因此必须要保证系统调用是可重入的
内核数据结构
内置了 方便遍历的单向链表，双向链表，环形链表 生产者消费者队列 映射 — 使用二叉搜索树实现而非散列表是因为在最坏情况下二叉搜索树的时间复杂度依然能保持在 logN 而不会像散列表那样退化到线性 存储大量数据而且需要检索迅速 — 红黑树
红黑树
是一种自平衡的二叉搜索树，维持半平衡结构，具有以下特性：
- 所有叶子节点非红即黑
- 叶子节点都是黑色
- 叶子节点不包含数据
- 所有非叶子节点都有两个子节点
- 一个节点是红，子节点必然都为黑
- 在任一节点到叶子节点的路径当中如果总包含相同数量的黑色节点，则该路径相比其他路径是最短的
为什么可以保证最深的叶子节点的深度不会大于两倍的最浅叶子节点深度？
一条路径可以是全黑或者红黑相间，如果黑色节点数量相同，那么最长的就是后者，最短的就为前者
中断
无须考虑与处理器的时钟同步，随时都可以打断内核，中断处理程序被内核调用并运行在特殊的中断上下文中
中断上下文也被称作原子上下文，内部的代码是不可阻塞不可抢占一直运行到结束的，因此它的处理程序必须在短时间内完成运行。
中断程序为什么不能睡眠？ 因为此时的执行上下文是不可恢复的，不能被重新调度的，必须迅速执行完
中断处理的上半部分：关中断的前提下对接收的中断进行应答（已注册的中断处理程序），能够被允许稍后完成的工作会被推迟到下半部，下半部是开中断的。硬件会提供状态寄存器供中断处理程序查询
中断处理程序都是预先在内核进行注册的回调函数，不同的函数位于不同的驱动程序中
- 安装驱动，初始化硬件
- 注册中断处理程序
- 注销中断处理程序
- 卸载驱动
中断处理程序是无须重入的，同一个中断处理程序不允许嵌套因为有中断程序运行时，对应中断线上的所有处理器都会被屏蔽掉，而其他线上的其他中断不受影响，因此同一个中断程序绝对不会被嵌套执行
中断处理程序使用被中断进程（没有进程执行时 空任务执行）的内核栈空间（32位8K两页，64位是4页16K）
中断的下半部
允许被中断的执行时间较长的处理程序都应当放在下半部分，但是这一部分依然是不允许重新调度或者睡眠的情况发生的
三种延迟内核工作的机制：
- 软中断 — 运行在中断上下文。编译时静态分配，适用于实时性和连续性较高的任务，例如网络 因为执行软中断的时候可能会被再次触发，因此可能会引发共享数据从而争抢锁的情况，一般可以采用单处理器中的数据来解决
一个被注册的软中断必须在被标记后执行，因此上半部分的任务大多是标记触发，然后下半部分通过进程中的检查来执行软中断程序
tasklet — 运行在中断上下文。运行时动态注册，使用方便，优先级比软中断要低 使用软中断实现，但与软中断不同的是，两个相同的 tasklet 不会同时执行，尽管不同的 tasklet 可以在不同处理器上运行 一个 tasklet 总在调度它的处理器上执行，因为能更好地利用 CPU 高速缓存
工作队列 — 唯一运行在进程上下文的中断下半部，存在内核线程的上下文切换开销
软中断的管理
因为软中断可以在执行的时候重新触发自己来再次得到执行，例如网络子系统。因此在大量软中断的时候需要有一组内核线程对这个过程进行监控来避免饥饿的情况
这个监控线程只要有空闲的处理器，就会处理软中断。同时又保证用户进程不会饥饿
工作队列 !!!
常见的推后工作的方式就是使用队列，重点是这种方式允许重新调度和睡眠 当然这也是唯一运行在进程上下文的下半部实现机制
本质上是一种接口：把需要推后执行的任务交给特定的通用线程（内核线程） 每个处理器对应一个线程，每个线程每次从队列（链表）中取一个工作函数出来并执行，循环往复 例如：获取大量内存，获取信号量，执行阻塞IO操作
同步机制
保护数据而不是源代码
死锁
最简单的死锁是自死锁，如果执行线程试图去获得一个自己已经持有的锁就会陷入忙等待的状态进而死锁
ABBA 死锁
预防死锁：
- 按顺序加锁
- 防止发生饥饿
- 不重复请求同一个锁
- 设计应该力求简单
加锁的粒度： 锁争用严重的时候，加锁太粗会降低可扩展性；当锁争用不明显的时候，加锁过细会加大系统的开销
内核提供的同步方法
- 原子操作 内联汇编指令实现，往往被定义成宏；与顺序性不同，原子性更强调互斥，不强调读写的先后
- 自旋锁 用于跨越一段临界区，没拿到锁的线程陷入忙等待，持有自旋锁的时间最好小于完成两次上下文切换的耗时，适用于短时间加锁
- 信号量 是一种睡眠锁，当不可用时会被推入一个等待队列，锁释放的时候再将等待队列中的任务唤醒并获得该信号量
- 互斥体 Mutex 是一种睡眠锁，适合长期加锁的场景
- 完成变量 与信号量作用差不多，让任务在一个变量上等待使得任务之间得以同步
- 顺序锁（乐观锁） 这种锁主要依靠一个序列计数器（相当于数据库里的版本记录），写者写入之后序列值会增加，如果在读取前和读取后的序列值相同，那么说明读操作没有被写操作打断过。 适用于读者多，写者少；而且写要优先于读的场景
屏障：通过读屏障和写屏障可以防止编译器重排读写某些共享数据的顺序！
定时器
节拍率有 k HZ，那么一个周期就是 1 / k 秒 x86默认的节拍率是 100 Hz 提高节拍率会有更高的时间解析度和精度，会使得依赖定时的任务能够执行得更准确，可以使进程抢占更准确，加快调度响应时间。坏处是给系统增加负担
实际时间
读取变量 xtime 的时候需要拿到顺序锁，读取时间需要不停地读直到确认没有被写操作修改过
定时器
通过动态地创建定时器并注册它的执行函数实现 一般来说定时器超时后马上就会执行，但也可能推迟到下一次时钟节拍才运行，因此定时器不适用于硬实时的任务
内核使用链表来存储定时器，但是为了提高效率，内核会将超时时间相近的定时器分配到一个组，减少检查超时的系统开销
延迟执行
- 忙等待：适用于延迟的时间是节拍的整数倍或精确度不高的情况。需要显式让内核进行重新调度
- 短延迟：适用于短暂的延迟，要求的延迟很精确。可以延迟的精度大于节拍数，因为每秒钟能运行的循环数是确定的，可以通过计算得到更高精度的延迟需要多少次循环。最小可以精确到 us 级别
内存管理
内存管理单元 MMU 以页的方式管理系统中的页表。从虚拟内存的角度上看，页就是最小的内存单元，页面的大小与体系结构相关。大多数 32 位体系结构支持 4KB 的页，64位的体系结构支持 8KB 的页表
页struct page 的属性：
- flags 表示页的状态
- _count 表示页的引用计数 — 当计数值变为 -1 是，表示这个页没有被引用，可以被页分配器重用进行新的分配
- virrual 域存放页的虚拟地址
这个结构体更偏向于物理页，因此它对页的描述是暂时的，内核仅仅用这个数据结构来描述当前时刻在相关物理页中存放的东西，只描述物理内存，不描述其中的数据 内核使用这个结构来管理系统中的每一个页，会占一些空间，但相对 4G 的内存大小来说不算什么
内存的区
内核并不是对所有的页都一视同仁的，因此需要对页进行区的划分，对具有相似功能的页进行分组
- ZONE_DMA ：DMA使用的页，使用的物理内存 < 16MB
- ZONE_NORMAL：正常可寻址的页， 16 ~ 896 M
- ZONE_HIGHMEM：动态映射的页，> 896 M
内核页分配规则：资源不紧张的时候，正常映射的页都从 ZONE_NORMAL 池中分配，如果资源紧张，可以尝试从 ZONE_DMA 分配。但 DMA 用途的页必须从 ZONE_DMA池中分配
值得注意的是 x86-64 没有 ZONE_HIGHMEM 高端内存区
页的分配与释放
内核提供一组接口来进行页的申请和释放 alloc_pages 分配 2的N次方个连续的物理页 填充为 0 值的物理页等 kmalloc() 获得以字节为单位的一块内核内存，连续的物理内存，性能更高 vmalloc() 获得在虚拟地址上是连续的内存，而在物理内存上不一定连续，需要构建页表项。与 malloc 类似，这就是用户空间分配页的方式，会产生较大的 TLB 抖动
slab 分配器作为通用数据结构的缓存层，来解决频繁的内存分配和释放导致的内存碎片的问题，负责内存紧缺下的所有底层的对齐，着色，分配和释放回收等问题
它的做法是把不同的对象划分成所谓的高速缓存组，每个缓存组都存放不同的对象，每种对象类型对应一个高速缓存，这一层被 kmalloc 所使用
高速缓存被划分为多个 slab，每个 slab 有多个连续的物理页，slab 对象有三种状态，满，部分满或空。当内核请求分配一个新的具体类型的对象的时候，分配器会优先从部分满和空的 slab 中获取
三种状态的 slab 使用链表串在一起。其中使用高速缓存进行快速的内存分配的例子出现在 fork 中，fork_init() 会创建高速缓存存放 task_struct，进程执行结束后如果没有子进程，进程描述符就会被释放并将内存返回给高速缓存
栈空间
用户空间的栈空间较大而内核栈空间小而固定 2 页，32位的为 8K ，64位的为 16K 当一页内核栈的选项激活的时候，中断处理程序就获得了自己的栈，而不是与被中断进程共享一个内核栈
在栈上进行静态分配是十分危险的，因为当栈溢出的时候第一时间波及的就是 thread_info ，任何内核数据都可能会有潜在的危险，因此采用动态分配是一种更佳的方案，能够及时发现溢出
x86 中，大于 896 M 的物理内存的范围大都是高端内存，这些页被分配时必须映射到内核的逻辑地址上，不能永久映射到内核的地址空间中
虚拟文件系统 VFS
不同的文件系统都依赖于 VFS 而得以共存 使得用户可以直接使用 open() read() write() 等系统调用而无需考虑具体文件系统，通过虚拟接口访问文件系统，使得这种协作性和泛型成为可能
write -> sys_write -> 具体文件系统的写方法 -> 物理介质 用户空间 VFS 具体文件系统
unix 的文件是一个有序的字节串，第一个字节是文件的头，最后一个字节是文件的尾，并面向字节流抽象
VFS 将目录也一并视为普通文件，这个文件列出了包含在其中的所有文件 unix 系统的文件相关信息和文件本身是相互分离的，文件的相关信息被单独存储在 inode 索引节点 中，文件系统的控制信息 存储在 超级块 中，超级块也包含文件系统信息
VFS 的实现采用面向对象的设计： 超级块对象 — 具体的已安装的文件系统 索引节点对象 — 具体文件（目录） 目录项对象 — 一个目录项，是路径的一个组成部分 文件对象 — 代表由进程打开的文件
每一个主要对象都包含一个操作对象，操作对象作为一个结构体指针来实现，包含操作其父对象的函数指针作为通用函数（C的泛型），如果通用函数满足不了需要，就必须使用实际文件系统独有的方法来填充这些函数指针
超级块对象
各种文件系统必须实现超级块对象，用于存储特定文件系统的信息，通常对应于存放在磁盘特定扇区中的文件系统超级块或文件系统控制块，非磁盘的文件系统会使用现场创建的超级块并将其保存在内存中
索引节点对象 inode
包含了内核在操作文件或目录时需要的全部信息，必须在内存中创建，以便于文件系统使用 仅当文件文件被访问时才在内存中创建 一个索引节点代表文件系统中的一个文件，也可以是设备或管道这样的特殊文件
inode 主要记录文件的属性以及该文件实际数据是放置在哪些 block，至少包含以下信息（不包含文件名！）：
- 文件大小，真正内容的 block 号
- 访问模式 rwx
- 拥有者和群组
- 各种时间戳
文件名存储在目录的 block 中
目录项对象
为了方便目录的查找，VFS引入了目录项，使得对路径字符串的比较过程更加简单 三种状态：被使用，未被使用和负状态。对象释放后也可以被保存到 slab 对象缓存中去
目录项会使用缓存来使得路径的查找能够快速执行，使用到了散列表和链表来构建缓存
文件对象
这是与进程直接打交道的对象，是已打开的文件在内存中的表示，文件对象通过指针域来指向相关的目录项对象指向索引节点来查看文件是否为脏（被修改）
根据文件路径读取文件的过程：
- 从高层级的目录的 inode 和 block 开始
- 通过挂载点信息找到 inode 号码对应的 inode，检查权限是否允许读，如果允许，根据读取 block 内容得到下一级的 inode 号码，递归进行
- 直到最后将文件的 block 读取出来
进程相关的其他数据结构
每个进程都有自己的一组打开的文件，64位机器中已打开文件的数组默认大小为 64 个，如果超过 64 个内核将分配一个新数组，用新的数组指针替换旧的
块 IO 层
块设备 — 随机访问，例如硬盘 字符设备 — 顺序访问，例如串口和键盘
块数据 block data
真正存放文件数据的地方，块大小格式化的时候就固定下来 每一个 block 都有编号，大小有 1K 2K 4K
块设备
块设备最小的可寻址单元是扇区，大小一般是 2 的整数倍，最常见的是 512 字节 块是文件系统的一种抽象，只能基于块来访问文件系统，块的大小只能是扇区大小的整数倍，通常块的大小是 512 B，1KB或4KB，但最大不能超过一个页面
当一个块被调入内存必须与一个缓冲区相对应，每个缓冲区都有一个对应的描述符
请求队列与IO调度
块设备将它们挂起的块 IO 请求保存在请求队列（双向链表）中，IO调度程序将磁盘IO分配给系统中所有挂起的块IO请求，这种资源分配是通过将请求队列中挂起的请求进行合并和排序来完成的，以便降低寻址时间
合并：多个请求合并为一个请求，相邻的扇区只请求一次，通过减少寻址命令来提高性能
电梯调度算法 — 向前合并排序，总是按照扇区顺序请求插入到队列，从不检查驻留时间过长的请求。缺点：会产生饥饿问题
最终期限调度算法：对于饥饿的问题的解决方案，对每个请求进行分类（读队列，写队列，排序队列）和确定超时时间，超时的请求会被优先从队列中取出并发送到派发队列（所有不同类的队列都会汇总到这里进行请求合并）。
预测IO调度算法：在最终期限调度的基础上增加了预测启发能力，不同之处在于请求提交之后不直接返回处理其他请求，而是有意空闲片刻，让应用程序有机会提交请求（可能又能多合并一波！）
进程地址空间
一个进程在32位的地址空间中可以寻址 4GB 的虚拟内存
进程只能访问有效内存区域内的内存地址，每个区域有自己的可读可写可执行的权限控制，如果进程访问了不再有效范围的内存区域，或以不正确的方式访问有效内存，内核就会终止该进程，并返回段错误信息
代码段 数据段 — 已初始化全局变量的内存映射 bss段 — 未初始化全局变量 进程用户栈 内存映射文件 共享内存段 堆 — 匿名内存映射
进程地址空间的具体表示使用内存描述符来描述，每个进程有唯一一个内存描述符
线程本质：父进程希望与子进程共享地址空间，在调用 clone() （fork 有用到）的时候设置 CLONE_VM 标志，把这样的进程称作线程，线程对内核来说仅仅是一个共享特定资源的进程而已
内核线程：没有进程地址空间，也没有内存描述符。不访问用户空间内存，但内核可以提供上一进程的内存描述符
mmap 域使用单独的链表连接内存区域对象，mm_rb 域使用红黑树连接所有内存区域对象，链表用于遍历而在地址空间中快速定位特定内存区域使用红黑树提高效率
页表
虚拟地址 -> 物理地址 需要将虚拟地址分段，使每段虚拟地址都作为索引指向页表，页表项则指向下一级别的页表或者指向最终的物理页面
linux 使用三级页表完成地址转换，多级页表可以显著降低存放空间。搜索页表的工作由硬件完成。 每个进程都有自己的页表，为了提高解析速度，会使用 TLB 作为虚拟地址映射到物理地址的硬件缓存
页高速缓存
页高速缓存是一种内核实现的磁盘缓存，用于减少对磁盘的 IO 操作。 通过把磁盘数据缓存到物理内存，把对磁盘的访问变为对物理内存的访问，通过占用空闲内存以扩张大小或者收缩来缓解内存使用压力。
进行读操作的时候会先检查是否在页高速缓存中，如果在就直接在内存中读取
写操作也是先写到缓存中，后端存储不会立即更新，而是将页高速缓存中被写的页面标记成脏，并加入脏页链表。最后由多个回写内核线程回写到磁盘中
缓存页的更新遵循双链策略，分为活跃链表和非活跃链表，使用 LRU/2 的策略。非活跃链表中的页缓存可以被换出回收
缓冲区高速缓存通过缓冲 来映射内存中的页面到磁盘块，减少寻找特定块的IO操作，往缓冲中先写入，再 flush 写入物理块中