- 第三章 进程管理
- 第四章 进程调度
- 第五章 系统调用
- 第六章 内核数据结构
- 第七章 中断和中断处理
- 第八章 下半部和退后执行的工作
- 第九章 内核同步介绍
- 第十章 内核同步方法
- 第十一章 定时器和时间管理
- 第十二章 内存管理
- 第十三章 虚拟文件系统
《Linux内核设计与实现》读书笔记
第三章 进程管理
- 每个处理器在任何时间点上的活动必然为三者之一：运行于用户空间，执行用户进程；运行于内核空间，处于进程上下文，代表某个进程的执行；运行于内核空间，处于中断上下文，与任何进程无关，处理某个特定的中断
- Linux内核不区分线程和进程，只是把线程看作是刚好要分享资源的进程
- 为了类型安全和易读性，优先使用内联函数而不是复杂的宏定义
- 内核开发的特点：
- 既不能访问C库也不能访问标准C头文件；但是内核中已经实现了类似的函数
- 必须使用GNU C
- 没有内存保护机制
- 难以执行浮点运算
- 内核中的每个进程只有一个很小的定长堆栈
- 编程时必须时刻注意同步和并发
- 可移植性
- 中断可以分为同步中断和异步中断：
- 同步中断（异常）：由CPU控制单元产生，只有在一条指令执行完毕后才会发出中断，因此称之为同步中断
- 异步中断（中断）：由其他硬件设备依据CPU的时钟信号随机产生，意味着中断能够在指令之间发生，因此称之为异步中断
- 异常向量表中的类型分为：中断；陷阱；故障；终止
- 在异常向量表中有一种异常叫做SysCall系统调用，它的类型是陷阱
- 中断和异常可以从不同的角度区分
- 进程是处于执行期的程序及其相关资源的总称
- 线程（执行线程）是在进程中活动的对象，每个线程都拥有一个程序计数器、进程栈和一组进程寄存器
- 内核调度的对象是线程而不是进程，Linux系统不特别区分进程和线程，线程只不过是一种特殊的进程罢了
- 线程之间可以共享虚拟内存，但每个线程都拥有各自的虚拟处理器
- fork子进程后，kernel有意选择子进程优先执行（但并非总是如此），因为一般调用子进程之后会立即调用exec，避免了拷贝父进程的内容，否则如果父进程先执行，很有可能会修改数据导致写时复制，这也说明了父进程和子进程的写入操作都会引起写时复制
- 系统调用陷入内核的本质就是软中断（准确来说应该是软件中断）引起的，这时会切换到进程的内核堆栈运行，系统调用完成后内核堆栈会恢复
- vfork与fork的不同：vfork是不拷贝页表项的，vfork会阻塞父进程直到子进程退出或者调用exec，子进程不能先父进程的地址空间写入
- 线程在Linux中的实现：通过传递给clone函数不同的参数来创建线程和进程，不同的参数表示不同的共享资源
- 进程终结时所需的清理工作和进程描述符的删除被分开执行，这样可以让系统在进程终结后仍能获得它的信息。在通知父进程后子进程的task_struct 才被释放
第四章 进程调度
- 进程可以分为I/O密集型和处理器密集型
- Linux中进程的优先级：
- nice值：取值-20~19，值越小优先级越高，表示进程时间片所占的比例
- 实时优先级：取值0~99，值越大优先级越高，实时进程优先级都高于普通进程
- 时间片：进程被抢占前所能持续运行的时间
- 在Linux中，nice值代表的是时间片的比例，具有更低nice值的进程会获得更高的比例
- CFS调度器抢占时机取决于新的可运行程序消耗的处理器使用比，如果消耗的处理器使用比比当前进程小，则抢占当前进程
- CFS调度器基本原理：设定一个调度周期，在这个调度周期内每个进程至少都会运行一次，根据进程的数量，平分这个调度周期内的CPU使用权，但是因为进程的优先级也就是nice值不同，分割调度周期的时候要加权；每个进程累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利
- CFS在Linux中的实现：
- 时间记账：通过调度器实体结构sched_entity中的vruntime实现，vruntime的计算:进程实际运行时间/当前进程总数
- 进程选择：选择vruntime最小的进程运行，通过rbtree实现
- 调度器入口：内核其他部分通过调用schedule()函数选择哪个进程可以运行，schedule()会选择最高优先级的调度类并且这个调度类有可运行的进程进行调度
- 睡眠和唤醒：
- 进入睡眠：进程把自己标记为睡眠状态（TASK_INTERRUPTIBLE或者TASK_UNINTERRUPTIBLE）;从可执行红黑树中移除；放入等待队列；调用schedule()选择执行下一个进程
- 唤醒：进程被设置为可执行状态；从等待队列中移到可执行红黑树中
- nice只会影响进程分到的处理器使用比，CFS调度器是依据vruntime来选择进程的
- 上下文切换：schedule()函数会调用contex_switch()处理上下文切换，主要的工作有：
- 把虚拟内存从上一个进程映射切换到当前进程
- 把处理器状态从上一个进程切换到当前进程
- 抢占：内核通过检查need_resched标志判断是否需要进行抢占
- 用户抢占：
- 从系统调用返回用户空间时
- 从中断处理程序返回用户空间时
- 内核抢占：
- 中断处理程序正在执行，且返回内核空间之前
- 内核代码再一次具有可抢占性的时候，比如释放锁的代码会检查need_resched是否被设置了
- 如果内核中的任务显示调用了schedule()
- 如果内核中的任务阻塞(这同样会导致调用schedule())
- 用户抢占：
- Linux调度策略
- SCHED_NORMAL:用于普通进程，调度算法为CFS
- SCHED_FIFO:用于实时进程；只有更高优先级的实时进程才能抢占；不基于时间片，一直运行直到进程阻塞或者显式释放处理器
- SCHED_RR:用于实时进程；带有时间片的SCHED_FIFO,进程时间片用完就被放到队尾
- 调度程序负责将哪个进程投入运行，何时运行以及运行多长时间
- 多任务系统可以分为抢占式多任务和非抢占式多任务
- 抢占：在抢占式多任务系统中，由调度程序决定什么时候停止一个进程的运行。这个强制挂起动作就叫做抢占(preemption)
- 让步：在非抢占式多任务系统中，除非进程自己主动停止运行，否则会它一直运行。进程主动挂起自己的操作成为让步(yielding)
- Linux为了保证交互式应用和桌面系统的响应，更倾向于优先调度I/O消耗型进程
第五章 系统调用
- 系统调用是用户空间访问内核的唯一手段；
- Unix接口设计有一句格言：提供机制而不是策略。这句话大概的意思是多抽象出一些适用性广的规则来，这样当具体情况有变时不用重新改规则
- 内核必须提供系统调用所希望完成的功能，但它完全可以按照自己预期的方式去实现，只要最后的结果正确就行了
- 用户空间的进程是通过系统调用号来指明要执行哪个系统调用，因此系统调用号不能更改，如果系统调用被删除了，那么这个系统调用号也必须保留
- 用户空间的进程通过触发软中断（Sys Call异常），促使系统切换到内核态执行异常处理程序，此处的异常处理程序就是系统调用处理程序，系统调用处理程序通过寄存器%eax获得系统调用号，再调用对应的系统调用
- 系统调用的上下文：此时内核处于进程的上下文，可以被抢占，因为新的进程同样可以使用相同的系统调用，因此要保证系统调用是可重入的
- 当系统调用返回的时候，控制权仍然在系统调用处理程序，它负责切换到用户空间，并让用户程序继续执行下去
- 处于进程上下文中允许睡眠，但是处于中断上下文不允许睡眠
- Linux中不提倡多用途的系统调用(不要像ioctl()那样)
- 建议开发者使用设备节点代替系统调用
第六章 内核数据结构
- 内核中链表的实现不是把数据结构塞入链表，而是把链表塞入数据结构中
#define offsetof(type,member) (size_t)&(((type*)0)->member) #define container_of(ptr, type, member) ({ \ const typeof (((type*)0)->member)* m_ptr = ptr;\ (type *)((char *)m_ptr-offsetof(type,member));\ }) - 内核中实现的队列为kfifo，可用于解决生产者消费者问题，需要注意的是队列是一块内存空间，可以插入任何类型的数据
- 内核中的映射idr：映射一个唯一的标识数(UID)到一个指针;比如用于将POSIX定时器ID映射到内核相关联的数据结构上
- 平衡二叉搜索树是一个所有叶子结点的深度差不超过1的二叉搜索树；深度可以理解为从根节点到这个结点的边数目
- 内核实现的红黑树称为rbtree，但是并没有提供搜索和插入的例程，需要用户自己实现
第七章 中断和中断处理
- 因为处理器的速度要远远比连接到计算机上的其他硬件要快，如果让处理器一直等待其他硬件显然会浪费资源，因此引入了中断机制，让其他硬件准备好了再通知处理器
- 中断：由其他硬件产生的异步中断；异常：由处理器产生的同步中断
- 在响应一个特定的中断的时候，内核会执行一个函数，这个函数被称为中断处理函数（interrupt handler）或者是中断服务例程（ISR）
- 中断处理程序与其他内核函数的真正区别在于：前者运行于中断上下文中，而中断上下文是不可阻塞的
- 中断处理程序切为两个部分：
- 上半部：接收到一个中断，它就立即执行，只做有严格时限的工作，例如对接收到的中断进行应答
- 下半部：能够被允许稍后完成的工作，下半部会被开中断执行
- 中断处理程序是设备驱动程序的组成部分,设备驱动程序通过request_irq函数注册中断处理程序
- request_irq函数可能会引起睡眠，因此不要在睡眠不安全的上下文中调用，其之所以会睡眠是由kmalloc函数引起的
- 比较重要的中断处理程序标志
- IRQF_DISABLED:设置该标志位，意味着在处理中断程序时要禁止其他所有的中断；否则中断处理程序可以与除本身外的其他任何中断同时运行
- IRQF_SHARED:设置该标志位，意味着同一条中断控制线可以有多个中断处理程序；否则一条中断控制线只能有一个中断处理程序
- free_irq:卸载驱动程序时需要注销相应的中断处理函数
- 如果指定了dev，那么不管中断线是否共享，都必须删除与dev匹配的中断处理程序
- 如果将被删除的中断处理程序是这条中断线上的最后一个，那么还会禁止该中断
- 初始化硬件和注册中断处理程序的顺序必须正确
- 卸载驱动程序时，需要通过free_irq释放中断处理程序
- Linux中的中断处理程序无须是可重入的，因为当前中断处理程序正在执行时，相应的中断线在所有处理器上都是被屏蔽的
- 在中断上下文中不可以睡眠，因为不能再重新调度中断，中断上下文不像进程上下文那样有一个task_struct
- 中断处理程序打断了其他代码，所以所有的中断处理程序都必须尽可能的迅速和简洁
- 在以前的内核中，中断是占用了被中断进程的内核栈，但是如今内核在每个处理器上都有一个中断栈
- 中断处理机制的实现：
- 硬件产生一个中断的电信号
- 中断控制器如果没有屏蔽这一路的中断，将信号传递给处理器
- 如果处理器没有禁止这一路中断，关闭中断系统，然后跳到初始入口点
- 初始入口点会在栈中保存中断号，并保存当前寄存器的值，然后调用do_IRQ函数
- do_IRQ函数根据中断号判断有没有对应的中断处理函数，如果有的话就会执行对应中断处理函数，最终调用另一个函数
- 在这个函数里面会调用schedule()重新调度，当schedule()返回的时候，恢复之前保存的寄存器，继续执行被中断的程序
- 中断处理过程：硬件产生一个中断的电信号，如果中断控制器没有屏蔽该中断，信号会传递给处理器，如果处理器没有禁止该中断，那么处理器就将响应该中断：处理器禁止所有中断，停止正在执行的程序， 根据异常向量表跳转到对应的位置，首先执行一段汇编代码在栈中保存中断号和被中断程序的寄存器值，然后调用do_IRQ函数，该函数会调用handle_IRQ_event函数，这个函数会调用该中断号对应的所有中断处理程序， 从do_IRQ返回到初始入口点，会再调用ret_from_intr函数，这个函数会检测系统是否需要重新调度，最后恢复被中断进程的寄存器，内核恢复到曾经中断的点继续执行
- 锁提供的保护机制：防止来自其他处理器对共享数据的并发访问
- 禁止中断提供的保护机制：防止来自其他中断处理程序的并发访问
- 当某段代码需要禁止本处理器上的中断时，要先保存中断的状态再禁止中断，之后再恢复保存的中断状态。而不是简单地开关中断
- 屏蔽多个中断处理程序共享的中断线是不合适的，因为这意味着屏蔽这条线上的所有设备
-
第八章 下半部和退后执行的工作
- 下半部的任务就是执行与中断处理密切相关但中断处理程序本身不执行的工作
- 上半部和下半部任务的划分
- 如果一个任务对时间非常敏感，将其放在中断处理程序中执行
- 如果一个任务和硬件相关，将其放在中断处理程序中执行
- 如果一个任务要保证不被其他中断(特别是相同的中断)打断，将其放在中断处理程序中执行
- 其他所有任务，考虑放在下半部执行
- 通常下半部在中断处理程序返回后马上执行，下半部执行的关键在于允许响应所有中断
- 在Linux中上半部从来只能通过中断处理程序实现，所以说这两个概念是等价的
- 下半部的实现机制：软中断和tasklet
- 软中断可以在所有处理器上同时执行；不同类型的tasklet可以在不同的处理器上同时执行
- tasklet基于软中断实现，是在性能和易用性之间寻求平衡的产物
- 软中断必须在编译期间静态注册；tasklet可以通过代码动态注册
- 在2.6版本的内核中提供了三种下半部实现机制：软中断、tasklets和工作队列
- 内核定时器可以把操作推迟到某个确定的时间段之后执行
- 一个软中断不会抢占另一个软中断，唯一可以抢占软中断的是中断处理程序
- 一个已经注册的软中断必须在被标记后才会运行，这被叫做触发软中断，中断处理程序在返回前会进行标记
- 软中断被检查和执行的时机：
- 从硬中断代码返回时
- 在ksoftirqd内核线程中
- 显式检查和执行待处理的软中断代码中
- 不管通过什么方式唤醒软中断，软中断都要在do_softirq()中执行
- 软中断保留给系统中对时间要求最严格以及最重要的下半部使用，内核定时器和tasklet都是建立在软中断之上
- 软中断可能在中断上下文或者进程上下文中执行，因此不允许睡眠
- 当执行软中断时，当前处理器会禁止软中断，因此不会进行抢占
- 两个相同的软中断可能会在不同处理器上执行，因此对共享数据要进行保护
- 使用软中断：
- 在软中断类型列表中添加新项
- 调用open_softirq()注册软中断函数
- 调用raise_softirq()设置软中断为挂起状态
- 在下次调用do_softirq()时会执行该软中断函数
- 为了优化，一个tasklet总在调度它的处理器上运行
- 当大量软中断出现的时候，内核会唤醒ksoftirqd线程来处理负载
- 工作队列：本质是创建内核线程的接口，可以被重新调度和睡眠
- worker thread：工作队列创建的线程称为工作者线程，在每个CPU上都有一个缺省的worker thread，叫做events/n；
- 推荐使用缺省的worker thread，但是也没有任何障碍防止开发者创建自己的worker thread
- 内核线程不能访问用户空间
- 当preempt_count为0时，下半部才能够被处理
第九章 内核同步介绍
- 临界区：访问和操作共享数据的代码段
- 竞争条件：两个执行线程有可能在同一个临界区中同时执行
- 同步：避免并发和防止竞争条件
- 为了避免在临界区中并发访问，操作在结束前不可被打断，就如同整个临界区是一个不可分割的指令
- 加锁是采用原子操作实现的，而原子操作不存在竞争
- 用户空间之所以需要同步，是因为用户程序会被调度程序抢占和重新调度
- 造成并发执行的原因（伪并行和真并行）
- 中断
- 软中断和中断的下半部
- 内核抢占
- 睡眠以及与用户空间的同步
- 对称多处理
- 用锁来保护共享资源并不困难，真正的挑战是辨认出需要共享的数据和相应的临界区
- 经验：如果有其他执行线程可以访问这些数据，那么就给这些数据加上某种形式的锁，要记住给数据而不是代码加锁
- 简单规则避免死锁：按顺序加锁，释放锁时最好按照加锁的相反顺序释放
- 当锁争用严重时，加锁太粗会降低可扩展性；而锁争用不明显时，加锁过细会加大系统开销
第十章 内核同步方法
- 原子操作：保证指令以原子方式执行，执行过程不被打断
- volatile关键字用来提醒编译器它定义的变量随时有可能改变，因此编译后的程序每次需要存储或读取这个变量的时候，都会直接从变量地址读取数据。如果没有volatile，编译器可能优化读取和存储，暂时使用寄存器中的值， 如果这个变量有别的程序更新了的话，将出现不一致现象
- 对一个字长数据的读取和写入总是原子地发生
- 内核提供了两组原子操作接口：
- 原子整数操作：只能对atomic_t类型的数据进行处理或者是64位的atomic_t64;最常见的用途是实现一个计数器
- 原子位操作： 对普通内存进行操作，没有特定的数据类型
- 原子性与顺序性：原子性确保指令在执行期间不被打断，要么全部执行完，要么根本不执行；顺序性保证的是指令的执行顺序
- 能使用原子操作时就尽量不要使用复杂的加锁机制
- 自旋锁(spin lock)：如果一个执行线程试图获得一个已经被持有的自旋锁，那么该线程就会一直进行忙等；如果锁未被争用，执行线程能够立即获得它
- 自旋锁的使用场景：
- 持有自旋锁的时间最好小于完成两次上下文切换的耗时
- 在单处理器上内核是没有自旋锁的，因为在这种体系结构上同一时间只能有一个进程，如果它请求的自旋锁失败，就会陷入忙等，直到它的时间片用完，代价非常大
- 自旋锁是不可递归的，如果试图获得一个自己持有的自旋锁，那么就会陷入永远的忙等中
- 自旋锁可以用在中断处理程序中，但是在内核代码获得自旋锁之前一定要关闭当前处理器的中断
- 持有自旋锁后不能够睡眠
- 自旋锁和下半部:
- 由于下半部可以抢占进程，所以当进程和下半部共享数据时，进程需要加锁和禁止下半部
- 由于上半部可以抢占下半部，在它们共享数据时，下半部也需要关中断
- 同类的tasklet不可能同时运行，因此不需要加锁
- 不同类的tasklet不会在同一个处理器上运行，只需要加锁不需要关下半部
- 同一处理器上的软中断不会抢占，只需要加锁不需要关下半部
- 读-写自旋锁：一个或多个读者可以并发地持有读者锁，但是写者锁最多只能被一个写任务持有；读者优先
- 如果加锁时间不长并且代码不会睡眠那么使用自旋锁是最佳选择
- 信号量是一种睡眠锁。如果一个任务试图获得一个不可用的信号量时，其会被推进一个等待队列，然后睡眠，这时处理器能重获自由；当信号量可用时，睡眠的任务将被唤醒并获得信号量；信号量的开销大于自旋锁
- 信号量使用场景：
- 适用于锁会被长时间持有的情况，因为睡眠、维护等待队列以及唤醒所花费的开销可能比锁占用的时间还要长
- 在进程上下文中才能使用
- 可以在持有锁的时候睡眠，因为试图获取当前锁的进程会睡眠而不会引起死锁
- 占用信号量的同时不能占用自旋锁
- 信号量：计数信号量和互斥信号量
- 如果请求的信号量被占用了，进程可能会进入TASK_INTERRUPTBLE或者TASK_UNINTERRUPTBLE状态,视使用的down函数决定
- 所有的读写信号量都是互斥信号量，读者的数量不限，写者只能有一个
- 读写锁的睡眠不会被信号打断，也就是说进程处于TASK_UNINTERRUPTBLE状态
- 读写信号量的down_read_trylock()和down_write_trylock()的返回值有点特别
- 读写信号量支持将写锁转换为读锁：downgrade_write()
- 因为大多数情况下信号量都是当成互斥量来使用，为了寻求一种更加简单的互斥量的使用方式，引入了互斥体
- 互斥体mutex的使用场景
- 给mutex上锁者必须给其解锁。不能在一个上下文中锁定一个mutex，而在另一个上下文中解锁
- 持有mutex的进程不可退出
- mutex不可在中断或者下半部中使用
- 也许mutex最有用的地方是可以配置内核的选项来调试，检测各种违反规定的行为
- 信号量和互斥体：两个容易混淆，但是除非互斥体的某个约定妨碍你使用，否则优先使用互斥体
- 自旋锁和互斥体：在中断上下文中只能使用自旋锁；互斥体会睡眠
- 完成变量：事实上完成变量只是提供了代替信号量的简单解决方法；例如当子进程执行或者退出时，vfork就会使用完成变量唤醒父进程
- 大内核锁(BKL)是一个全局自旋锁
- BKL使用场景：
- 持有BKL的任务仍然可以睡眠，如果任务被挂起则会自动释放锁，重新调度时自动获得锁
- BKL是一种递归锁，并不会像自旋锁那样产生死锁
- BKL只能在进程上下文中使用，不能在中断上下文中使用
- 持有BKL锁时内核禁止抢占
- 不鼓励使用BKL
- 顺序锁：实现这种锁主要依靠一个计数器，当写者获取或者释放锁时都会使计数值加一；读者在读取数据的前后都会读取计数值，如果前后计数值一致说明数据是正确的，否则会一直循环读取数据并判断计数值
- 顺序锁的使用场景：
- 存在很多读者
- 存在很少写者
- 希望写着优先读者，并且不希望读者让写者饥饿
- 内核禁止抢占：
- 使用自旋锁作为非抢占区域的标记
- 如果这是每个处理器上独立的变量，那么可能就不需要锁，只需要简单地关闭内核抢占即可
- 抢占计数存放着被持有锁的数量和preempt_disable()的调用次数，如果抢占计数为0，那么内核可以进行抢占；否则内核不会进行抢占
- 虽然禁止内核抢占但是还是可以进行调度的
- 屏障：有些编译器和处理器出于优化的目的，可能会对读和写重新排序，确保读写顺序的指令称为屏障
- rmb
- wmb
- mb
- 编译器屏障barrier()
第十一章 定时器和时间管理
第十二章 内存管理
- 由于硬件限制，内核不能对所有的内存页一视同仁，所以把内存页划分为不同的区(zone)，在不同的体系结构上是不同的，在x86-32上分别是ZONE_DMA,ZONE_NORMAL,ZONE_HIGHMEM;但是在x86-64上是没有高端内存的
- 区的划分没有任何物理意义，只不过是内核为了管理页而采取的一种逻辑上的分组
- kmalloc确保分配的内存在物理地址上是连续的(虚拟地址自然也是连续的)，vmalloc只是保证虚拟地址连续，物理地址不一定连续；大多数情况下只有硬件设备才要求物理地址连续
- vmalloc在发生错误时可能会睡眠，所以不能在不允许阻塞的情况下调用；只有在不得已的情况才会使用vmalloc，例如申请大块内存的时候：动态加载内核模块
- slab层：通用数据结构缓冲层
- slab层把不同的对象划分为不同的高速缓存
- 高速缓存又被划分为许多slab，slab是由一个或多个连续的物理页组成
- slab的状态：满，半满，空闲
- 分配时先从半满的分配，如果没有半满的就从空闲的slab分配，这种策略能减少碎片
- kmalloc建立在slab层之上
- 内核栈非常小并且固定，由于内核没有在内核栈的管理上做足工作，当内核栈溢出时悄无声息，会覆盖掉周围的内存，因此进行动态分配内存是一种明智的决定
- 高端内存的映射：永久映射和临时映射
- 使用每个CPU数据的好处：
- 可能不再需要锁
- 大大减少缓存失败
- 在访问每个CPU数据时不能够睡眠，如果睡眠了，那么醒来你可能就在另一个处理器上了
- 用户空间和内核空间
- 所有进程共享同一个内核空间
- 用户空间和内核空间都是使用虚拟地址空间
- 用户空间存放用户进程的代码和数据，内核空间存放内核的代码和数据
- 当进程运行在用户空间时称为用户态；当进程通过系统调用进入内核空间运行时称为内核态
- Linux内部架构
