linux内核设计与实现 怎样

译者序序言前言作者简介第1章　Linux内核简介11.1　Unix的历史11.2　追寻Linus足迹：Linux简介21.3　 *** 作系统和内核简介31.4　Linux内核和传统Unix内核的比较51.5　Linux内核版本71.6　Linux内核开发者社区81.7　小结8第2章　从内核出发102.1　获取内核源码102.1.1　使用Git102.1.1　安装内核源代码102.1.3　使用补丁112.2　内核源码树112.3　编译内核122.3.1　配置内核122.3.2　减少编译的垃圾信息142.3.3　衍生多个编译作业 142.3.4　安装新内核142.4　内核开发的特点152.4.1　无libc库抑或无标准头文件152.4.2　GNU C162.4.3　没有内存保护机制182.4.4　不要轻易在内核中使用浮点数182.4.5　容积小而固定的栈182.4.6　同步和并发182.4.7　可移植性的重要性192.5　小结19第3章　进程管理203.1　进程203.2　进程描述符及任务结构 213.2.1　分配进程描述符223.2.2　进程描述符的存放233.2.3　进程状态233.2.4　设置当前进程状态253.2.5　进程上下文253.2.6　进程家族树253.3　进程创建263.3.1　写时拷贝273.3.2　fork()273.3.3　vfork()283.4　线程在Linux中的实现283.4.1　创建线程293.4.2　内核线程303.5　进程终结313.5.1　删除进程描述符323.5.2　孤儿进程造成的进退维谷323.6　小结34第4章　进程调度354.1　多任务354.2　Linux 的进程调度364.3　策略364.3.1　I/O消耗型和处理器消耗型的进程364.3.2　进程优先级374.3.3　时间片384.3.4　调度策略的活动384.4　Linux调度算法394.4.1　调度器类394.4.2　Unix 系统中的进程调度404.4.3　公平调度414.5　Linux调度的实现424.5.1　时间记账424.5.2　进程选择444.5.3　调度器入口484.5.4　睡眠和唤醒494.6　抢占和上下文切换514.6.1　用户抢占534.6.2　内核抢占534.7　实时调度策略544.8　与调度相关的系统调用544.8.1　与调度策略和优先级相关的系统调用554.8.2　与处理器绑定有关的系统调用554.8.3　放弃处理器时间564.9　小结56第5章　系统调用575.1　与内核通信575.2　API、POSIX和C库575.3　系统调用585.3.1　系统调用号595.3.2　系统调用的性能595.4　系统调用处理程序605.4.1　指定恰当的系统调用605.4.2　参数传递605.5　系统调用的实现615.5.1　实现系统调用615.5.2　参数验证625.6　系统调用上下文645.6.1　绑定一个系统调用的最后步骤655.6.2　从用户空间访问系统调用675.6.3　为什么不通过系统调用的方式实现685.7　小结68第6章　内核数据结构696.1　链表696.1.1　单向链表和双向链表696.1.2　环形链表706.1.3　沿链表移动716.1.4　Linux 内核中的实现716.1.5　 *** 作链表736.1.6　遍历链表756.2　队列786.2.1　kfifo796.2.2　创建队列796.2.3　推入队列数据796.2.4　摘取队列数据806.2.5　获取队列长度806.2.6　重置和撤销队列806.2.7　队列使用举例 816.3　映射 816.3.1　初始化一个idr826.3.2　分配一个新的UID826.3.3　查找UID836.3.4　删除UID846.3.5　撤销idr846.4　二叉树846.4.1　二叉搜索树846.4.2　自平衡二叉搜索树 856.5　数据结构以及选择 876.6　算法复杂度886.6.1　算法886.6.2　大o 符号886.6.3　大θ符号896.6.4　时间复杂度896.7　小结 90第7章　中断和中断处理917.1　中断917.2　中断处理程序927.3　上半部与下半部的对比937.4　注册中断处理程序937.4.1　中断处理程序标志947.4.2　一个中断例子957.4.3　释放中断处理程序957.5　编写中断处理程序967.5.1　共享的中断处理程序977.5.2　中断处理程序实例977.6　中断上下文997.7　中断处理机制的实现1007.8　/proc/interrupts1027.9　中断控制1037.9.1　禁止和激活中断1037.9.2　禁止指定中断线1057.9.3　中断系统的状态1057.10　小结106第8章　下半部和推后执行的工作1078.1　下半部1078.1.1　为什么要用下半部1088.1.2　下半部的环境1088.2　软中断1108.2.1　软中断的实现1118.2.2　使用软中断1138.3　tasklet1148.3.1　tasklet的实现1148.3.2　使用tasklet1168.3.3　老的BH机制1198.4　工作队列1208.4.1　工作队列的实现1218.4.2　使用工作队列1248.4.3　老的任务队列机制1268.5　下半部机制的选择1278.6　在下半部之间加锁1288.7　禁止下半部1288.8　小结129第9章　内核同步介绍1319.1　临界区和竞争条件1319.1.1　为什么我们需要保护1329.1.2　单个变量1339.2　加锁1349.2.1　造成并发执行的原因1359.2.2　了解要保护些什么1369.3　死锁1379.4　争用和扩展性1389.5　小结140第10章　内核同步方法14110.1　原子 *** 作14110.1.1　原子整数 *** 作14210.1.2　64位原子 *** 作14410.1.3　原子位 *** 作14510.2　自旋锁14710.2.1　自旋锁方法14810.2.2　其他针对自旋锁的 *** 作14910.2.3　自旋锁和下半部15010.3　读-写自旋锁15010.4　信号量15210.4.1　计数信号量和二值信号量15310.4.2　创建和初始化信号量15410.4.3　使用信号量15410.5　读-写信号量15510.6　互斥体15610.6.1　信号量和互斥体15810.6.2　自旋锁和互斥体15810.7　完成变量15810.8　BLK：大内核锁15910.9　顺序锁16010.10　禁止抢占16110.11　顺序和屏障16210.12　小结165第11章　定时器和时间管理16611.1　内核中的时间概念16611.2　节拍率：HZ16711.2.1　理想的HZ值16811.2.2　高HZ的优势16911.2.3　高HZ的劣势16911.3　jiffies17011.3.1　jiffies的内部表示17111.3.2　jiffies 的回绕17211.3.3　用户空间和HZ17311.4　硬时钟和定时器17411.4.1　实时时钟17411.4.2　系统定时器17411.5　时钟中断处理程序17411.6　实际时间17611.7　定时器17811.7.1　使用定时器17811.7.2　定时器竞争条件18011.7.3　实现定时器18011.8　延迟执行18111.8.1　忙等待18111.8.2　短延迟18211.8.3　schedule_timeout()18311.9　小结185第12章　内存管理18612.1　页18612.2　区18712.3　获得页18912.3.1　获得填充为0的页19012.3.2　释放页19112.4　kmalloc()19112.4.1　gfp_mask标志19212.4.2　kfree()19512.5　vmalloc()19612.6　slab层19712.6.1　slab层的设计19812.6.2　slab分配器的接口20012.7　在栈上的静态分配20312.7.1　单页内核栈20312.7.2　在栈上光明正大地工作20312.8　高端内存的映射20412.8.1　永久映射20412.8.2　临时映射20412.9　每个CPU的分配20512.10　新的每个CPU接口20612.10.1　编译时的每个CPU数据20612.10.2　运行时的每个CPU数据20712.11　使用每个CPU数据的原因20812.12　分配函数的选择20912.13　小结209第13章　虚拟文件系统21013.1　通用文件系统接口21013.2　文件系统抽象层21113.3　Unix文件系统21213.4　VFS 对象及其数据结构21313.5　超级块对象21413.6　超级块 *** 作21513.7　索引节点对象21713.8　索引节点 *** 作21913.9　目录项对象22213.9.1　目录项状态22213.9.2　目录项缓存22313.10　目录项 *** 作22413.11　文件对象22513.12　文件 *** 作22613.13　和文件系统相关的数据结构23013.14　和进程相关的数据结构23213.15　小结233第14章　块I/O层23414.1　剖析一个块设备23414.2　缓冲区和缓冲区头23514.3　bio结构体23714.3.1　I/O向量23814.3.2　新老方法对比23914.4　请求队列24014.5　I/O调度程序24014.5.1　I/O调度程序的工作24114.5.2　Linus 电梯24114.5.3　最终期限I/O调度程序24214.5.4　预测I/O调度程序24414.5.5　完全公正的排队I/O调度程序24414.5.6　空 *** 作的I/O调度程序24514.5.7　I/O调度程序的选择24514.6　小结246第15章　进程地址空间24715.1　地址空间24715.2　内存描述符24815.2.1　分配内存描述符24915.2.2　撤销内存描述符25015.2.3　mm_struct 与内核线程25015.3　虚拟内存区域25115.3.1　VMA标志25115.3.2　VMA *** 作25315.3.3　内存区域的树型结构和内存区域的链表结构25415.3.4　实际使用中的内存区域25415.4　 *** 作内存区域25515.4.1　find_vma()25615.4.2　find_vma_prev()25715.4.3　find_vma_intersection()25715.5　mmap()和do_mmap()：创建地址区间25815.6　mummap()和do_mummap()：删除地址区间25915.7　页表26015.8　小结261第16章　页高速缓存和页回写26216.1　缓存手段26216.1.1　写缓存26216.1.2　缓存回收26316.2　Linux 页高速缓存26416.2.1　address_space对象26416.2.2　address_space *** 作26616.2.3　基树26716.2.4　以前的页散列表26816.3　缓冲区高速缓存26816.4　flusher线程26816.4.1　膝上型计算机模式27016.4.2　历史上的bdflush、kupdated 和pdflush27016.4.3　避免拥塞的方法：使用多线程27116.5　小结271第17章　设备与模块27317.1　设备类型27317.2　模块27417.2.1　Hello，World27417.2.2　构建模块27517.2.3　安装模块27717.2.4　产生模块依赖性27717.2.5　载入模块27817.2.6　管理配置选项27917.2.7　模块参数28017.2.8　导出符号表28217.3　设备模型28317.3.1　kobject28317.3.2　ktype28417.3.3　kset28517.3.4　kobject、ktype和kset的相互关系28517.3.5　管理和 *** 作kobject28617.3.6　引用计数28717.4　sysfs28817.4.1　sysfs中添加和删除kobject 29017.4.2　向sysfs中添加文件29117.4.3　内核事件层29317.5　小结294第18章　调试29518.1　准备开始29518.2　内核中的bug29618.3　通过打印来调试29618.3.1　健壮性29618.3.2　日志等级29718.3.3　记录缓冲区29818.3.4　syslogd和klogd29818.3.5　从printf()到printk()的转换29818.4　oops29818.4.1　ksymoops30018.4.2　kallsyms30018.5　内核调试配置选项30118.6　引发bug并打印信息30118.7　神奇的系统请求键30218.8　内核调试器的传奇30318.8.1　gdb30318.8.2　kgdb30418.9　探测系统30418.9.1　用UID作为选择条件30418.9.2　使用条件变量30518.9.3　使用统计量30518.9.4　重复频率限制30518.10　用二分查找法找出引发罪恶的变更30618.11　使用Git进行二分搜索30718.12　当所有的努力都失败时：社区30818.13　小结308第19章　可移植性30919.1　可移植 *** 作系统30919.2　Linux移植史31019.3　字长和数据类型31119.3.1　不透明类型31319.3.2　指定数据类型31419.3.3　长度明确的类型31419.3.4　char型的符号问题31519.4　数据对齐31519.4.1　避免对齐引发的问题31619.4.2　非标准类型的对齐31619.4.3　结构体填补31619.5　字节顺序31819.6　时间31919.7　页长度32019.8　处理器排序32019.9　SMP、内核抢占、高端内存32119.10　小结321第20章　补丁、开发和社区32220.1　社区32220.2　Linux编码风格32220.2.1　缩进32320.2.2　switch 语句32320.2.3　空格32420.2.4　花括号32520.2.5　每行代码的长度32620.2.6　命名规范32620.2.7　函数32620.2.8　注释32620.2.9　typedef32720.2.10　多用现成的东西32820.2.11　在源码中减少使用ifdef32820.2.12　结构初始化32820.2.13　代码的事后修正32920.3　管理系统32920.4　提交错误报告32920.5　补丁33020.5.1　创建补丁33020.5.2　用Git创建补丁33120.5.3　提交补丁33120.6　小结332参考资料333

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统，是像Linux这样的多任务 *** 作系统的基础。

多任务 *** 作系统就是能同时并发地交互执行多个进程的 *** 作系统。可以分为两类：

进程可以分为I/O消耗型和处理器消耗型（进程可以同时展示这两种行为）。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率。Linux为了保证交互式应用和桌面系统的性能，对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。

Linux采用了两种不同的优先级范围：

实时优先级和nice值处于互不相交的两个范畴，任何实时进程的优先级都高于普通进程。

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

Linux自2.6内核系统开始引入新的进程调度算法，其中最著名的是“反转楼梯最后期限调度算法（rotating staircase deadline scheduler，RSDL）”，被称为“完成公平调度算法（CFS）”。

Linux的CFS调度器并没有直接分配时间片到进程，而是将处理器的使用比例划分给进程，也就是说，进程所获得的处理器时间和系统负载密切相关的。当一个进程进入可运行状态，他就被准许投入运行。Linux的CFS调度器，其抢占时机取决于新的可运行进程消耗了多少处理器使用比。如果消耗的使用比例比当前进程小，则新的进程立刻投入运行，抢占当前进程，否则推迟运行。

Linux调度器是以模块方式提供的，以允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础调度器会按照优先级顺序进程遍历调度类，拥有一个可执行进程的最高优先级的调度类胜出，去选择接下来要执行的程序。

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行的进程。nice值作为进程获得的处理器运行比的权重，nice值越低权重越高。每个进程都按照其权重在全部可行进程中所占比例的“时间片”来运行，任何进程所获的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标，称为目标延迟。

CFS调度算法的实现，主要关注：

所有的调度器都必须对进程运行时间做记账。CFS通过时间记账确保每个进程只在公平分配给它的处理器时间内运行。

CFS使用调度器实体结构来追踪进程运行记账，该结构为进程描述符（struct task_struct的成员变量）：

vruntime变量存放进程的虚拟运行时间，经过了所有可运行进程总数的标准化（被加权的）。以ns为单位，和定时器节拍不相关。CFS使用vruntime来记录一个程序到底运行了多长时间以及它还应该再运行多久。

update_curr()函数实现了记账功能。是由系统定时器周期性调用的，无论进程处于可运行态，还是不可运行态。因此，vruntime可以准确地测量给定进程的运行时间，而且知道谁是应该被下一个运行的进程。

CFS算法的核心：选择具有最小的vruntime任务。

CFS使用红黑树（rbtree）来组织可运行进程队列，其节点的键值为可运行进程的虚拟运行时间vruntime，有利于迅速找到最小vruntime的进程（可通过__pick_next_entity()函数来访问红黑树最左的叶子即可，当然最左的叶子可能被缓存在rb_left_most字段中，可直接读取）。

另外，可通过enqueue_entity/dequeue_entity函数从红黑树中增加/删除进程。这两个函数都会调用update_curr()函数来更新所处理任务的运行时统计数据。

进程调度的主要入口点是schedule()函数，是内核其他部分用于调用进程调度器的入口：选择哪个进程运行，何时将其投入运行。schedule()函数会通过pick_next_task()函数遍历调度类，找出优先级最高的调度类（struct sched_class），再通过调度类的pick_next_entity()函数（会调用__pick_next_entity()函数）来选择要执行的进程。

休眠（被阻塞）的进程处于不可运行的状态。内核对其 *** 作是：进程把自己标记称休眠状态，从可执行红黑树中删除，放入等待队列，然后调用schedule()选择和执行下一个进程。

唤醒：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

其中，等待队列是由等待某些事件发生的进程组成的简单链表。

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由context_switch函数处理。

用户抢占：

Linux完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。只要没有持有锁，内核就可以进行抢占。内核抢占主要发生在：

普通的、非实时的调度策略是SCHED_NORMAL。

Linux提供两种实时调度策略：

Linux为实时调度策略提供一种软实时工作方式。也就是内核调度进程，尽力使进程在它的限定时间内运行，但内核不保证总能满足这些进程的要求。

对应的，硬实时系统保证在一定条件下，可以满足任何调度的要求。

七、与调度相关的系统调用

---