Linux内核设计与实现（原书第3版·典藏版）

本书基于Linux 2.6.34内核详细介绍了Linux内核系统，覆盖了从核心内核系统的应用到内核设计与实现等各方面内容。主要内容包括：进程管理、进程调度、时间管理和定时器、系统调用接口、内存寻址、内存管理和页缓存、VFS、内核同步以及调试技术等。同时本书也涵盖了Linux 2.6内核中颇具特色的内容，包括CFS调度程序、抢占式内核、块I/O层以及I/O调度程序等。本书采用理论与实践相结合的路线，能够带领读者快速走进Linux内核世界，真正开发内核代码。本书适合作为高等院校操作系统课程的教材或参考书，也可供相关技术人员参考。

罗伯特·洛夫（Robert Love）资深的开源软件开发者，很早就开始使用Linux。目前是谷歌云的高级工程总监，在那里构建了全球范围的网络产品。在此之前，他曾是Toast的工程副总裁，开发Android移动平台内核的团队成员，Novell公司Linux桌面系统首席架构师。<br /> 他参与的内核项目包括抢占式内核、进程调度器、内核事件层、通知机制、VM改进，以及设备驱动程序。他曾是Linux Journal杂志的编辑。除本书之外，他还著有Linux System Programming和Linux in a Nutshell。

目　　录<br /><br />译者序<br />序　言<br />前　言<br />第3版致谢<br />作者简介<br /><br />第1章　Linux内核简介1<br />1.1　UNIX的历史1<br />1.2　追寻Linus足迹：Linux简介2<br />1.3　操作系统和内核简介3<br />1.4　Linux内核和传统UNIX内核的<br />比较5<br />1.5　Linux内核版本7<br />1.6　Linux内核开发者社区8<br />1.7　小结8<br />第2章　从内核出发10<br />2.1　获取内核源码10<br />2.1.1　使用Git10<br />2.1.2　安装内核源代码10<br />2.1.3　使用补丁11<br />2.2　内核源码树11<br />2.3　编译内核12<br />2.3.1　配置内核12<br />2.3.2　减少编译的垃圾信息14<br />2.3.3　衍生多个编译作业 14<br />2.3.4　安装新内核14<br />2.4　内核开发的特点15<br />2.4.1　无libc库抑或无标准头文件15<br />2.4.2　GNU C16<br />2.4.3　没有内存保护机制18<br />2.4.4　不要轻易在内核中使用浮点数18<br />2.4.5　容积小而固定的栈18<br />2.4.6　同步和并发18<br />2.4.7　可移植性的重要性19<br />2.5　小结19<br />第3章　进程管理20<br />3.1　进程20<br />3.2　进程描述符及任务结构 21<br />3.2.1　分配进程描述符22<br />3.2.2　进程描述符的存放23<br />3.2.3　进程状态23<br />3.2.4　设置当前进程状态25<br />3.2.5　进程上下文25<br />3.2.6　进程家族树25<br />3.3　进程创建26<br />3.3.1　写时拷贝27<br />3.3.2　fork()27<br />3.3.3　vfork()28<br />3.4　线程在Linux中的实现28<br />3.4.1　创建线程29<br />3.4.2　内核线程30<br />3.5　进程终结31<br />3.5.1　删除进程描述符32<br />3.5.2　孤儿进程造成的进退维谷32<br />3.6　小结34<br />第4章　进程调度35<br />4.1　多任务35<br />4.2　Linux 的进程调度36<br />4.3　策略36<br />4.3.1　I/O消耗型和处理器消耗型的<br />进程36<br />4.3.2　进程优先级37<br />4.3.3　时间片38<br />4.3.4　调度策略的活动38<br />4.4　Linux调度算法39<br />4.4.1　调度器类39<br />4.4.2　UNIX 系统中的进程调度40<br />4.4.3　公平调度41<br />4.5　Linux调度的实现42<br />4.5.1　时间记账42<br />4.5.2　进程选择44<br />4.5.3　调度器入口48<br />4.5.4　睡眠和唤醒49<br />4.6　抢占和上下文切换51<br />4.6.1　用户抢占53<br />4.6.2　内核抢占53<br />4.7　实时调度策略54<br />4.8　与调度相关的系统调用54<br />4.8.1　与调度策略和优先级相关的<br />系统调用55<br />4.8.2　与处理器绑定有关的系统调用55<br />4.8.3　放弃处理器时间56<br />4.9　小结56<br />第5章　系统调用57<br />5.1　与内核通信57<br />5.2　API、POSIX和C库57<br />5.3　系统调用58<br />5.3.1　系统调用号59<br />5.3.2　系统调用的性能59<br />5.4　系统调用处理程序60<br />5.4.1　指定恰当的系统调用60<br />5.4.2　参数传递60<br />5.5　系统调用的实现61<br />5.5.1　实现系统调用61<br />5.5.2　参数验证62<br />5.6　系统调用上下文64<br />5.6.1　绑定一个系统调用的最后步骤65<br />5.6.2　从用户空间访问系统调用67<br />5.6.3　为什么不通过系统调用的<br />方式实现68<br />5.7　小结68<br />第6章　内核数据结构69<br />6.1　链表69<br />6.1.1　单向链表和双向链表69<br />6.1.2　环形链表70<br />6.1.3　沿链表移动71<br />6.1.4　Linux 内核中的实现71<br />6.1.5　操作链表73<br />6.1.6　遍历链表75<br />6.2　队列78<br />6.2.1　kfifo79<br />6.2.2　创建队列79<br />6.2.3　推入队列数据79<br />6.2.4　摘取队列数据80<br />6.2.5　获取队列长度80<br />6.2.6　重置和撤销队列80<br />6.2.7　队列使用举例 81<br />6.3　映射 81<br />6.3.1　初始化一个idr82<br />6.3.2　分配一个新的UID82<br />6.3.3　查找UID83<br />6.3.4　删除UID84<br />6.3.5　撤销idr84<br />6.4　二叉树84<br />6.4.1　二叉搜索树84<br />6.4.2　自平衡二叉搜索树 85<br />6.5　数据结构以及选择 87<br />6.6　算法复杂度88<br />6.6.1　算法88<br />6.6.2　大o 符号88<br />6.6.3　大θ符号89<br />6.6.4　时间复杂度89<br />6.7　小结 90<br />第7章　中断和中断处理91<br />7.1　中断91<br />7.2　中断处理程序92<br />7.3　上半部与下半部的对比93<br />7.4　注册中断处理程序93<br />7.4.1　中断处理程序标志94<br />7.4.2　一个中断例子95<br />7.4.3　释放中断处理程序95<br />7.5　编写中断处理程序96<br />7.5.1　共享的中断处理程序97<br />7.5.2　中断处理程序实例97<br />7.6　中断上下文99<br />7.7　中断处理机制的实现100<br />7.8　/proc/interrupts102<br />7.9　中断控制103<br />7.9.1　禁止和激活中断103<br />7.9.2　禁止指定中断线105<br />7.9.3　中断系统的状态105<br />7.10　小结106<br />第8章　下半部和推后执行的<br />工作107<br />8.1　下半部107<br />8.1.1　为什么要用下半部108<br />8.1.2　下半部的环境108<br />8.2　软中断110<br />8.2.1　软中断的实现111<br />8.2.2　使用软中断113<br />8.3　tasklet114<br />8.3.1　tasklet的实现114<br />8.3.2　使用tasklet116<br />8.3.3　老的BH机制119<br />8.4　工作队列120<br />8.4.1　工作队列的实现121<br />8.4.2　使用工作队列124<br />8.4.3　老的任务队列机制126<br />8.5　下半部机制的选择127<br />8.6　在下半部之间加锁128<br />8.7　禁止下半部128<br />8.8　小结129<br />第9章　内核同步介绍131<br />9.1　临界区和竞争条件131<br />9.1.1　为什么我们需要保护132<br />9.1.2　单个变量133<br />9.2　加锁134<br />9.2.1　造成并发执行的原因135<br />9.2.2　了解要保护些什么136<br />9.3　死锁137<br />9.4　争用和扩展性138<br />9.5　小结140<br />第10章　内核同步方法141<br />10.1　原子操作141<br />10.1.1　原子整数操作142<br />10.1.2　64位原子操作144<br />10.1.3　原子位操作145<br />10.2　自旋锁147<br />10.2.1　自旋锁方法148<br />10.2.2　其他针对自旋锁的操作149<br />10.2.3　自旋锁和下半部150<br />10.3　读-写自旋锁150<br />10.4　信号量152<br />10.4.1　计数信号量和二值信号量153<br />10.4.2　创建和初始化信号量154<br />10.4.3　使用信号量154<br />10.5　读-写信号量155<br />10.6　互斥体156<br />10.6.1　信号量和互斥体158<br />10.6.2　自旋锁和互斥体158<br />10.7　完成变量158<br />10.8　BLK：大内核锁159<br />10.9　顺序锁160<br />10.10　禁止抢占161<br />10.11　顺序和屏障162<br />10.12　小结165<br />第11章　定时器和时间管理166<br />11.1　内核中的时间概念166<br />11.2　节拍率：Hz167<br />11.2.1　理想的Hz值168<br />11.2.2　高Hz的优势169<br />11.2.3　高Hz的劣势169<br />11.3　jiffies170<br />11.3.1　jiffies的内部表示171<br />11.3.2　jiffies 的回绕172<br />11.3.3　用户空间和Hz173<br />11.4　硬时钟和定时器174<br />11.4.1　实时时钟174<br />11.4.2　系统定时器174<br />11.5　时钟中断处理程序174<br />11.6　实际时间176<br />11.7　定时器178<br />11.7.1　使用定时器178<br />11.7.2　定时器竞争条件180<br />11.7.3　实现定时器180<br />11.8　延迟执行181<br />11.8.1　忙等待181<br />11.8.2　短延迟182<br />11.8.3　schedule_timeout()183<br />11.9　小结185<br />第12章　内存管理186<br />12.1　页186<br />12.2　区187<br />12.3　获得页189<br />12.3.1　获得填充为0的页190<br />12.3.2　释放页191<br />12.4　kmalloc()191<br />12.4.1　gfp_mask标志192<br />12.4.2　kfree()195<br />12.5　vmalloc()196<br />12.6　slab层197<br />12.6.1　slab层的设计198<br />12.6.2　slab分配器的接口200<br />12.7　在栈上的静态分配203<br />12.7.1　单页内核栈203<br />12.7.2　在栈上光明正大地工作203<br />12.8　高端内存的映射204<br />12.8.1　永久映射204<br />12.8.2　临时映射204<br />12.9　每个CPU的分配205<br />12.10　新的每个CPU接口206<br />12.10.1　编译时的每个CPU数据206<br />12.10.2　运行时的每个CPU数据207<br />12.11　使用每个CPU数据的原因208<br />12.12　分配函数的选择209<br />12.13　小结209<br />第13章　虚拟文件系统210<br />13.1　通用文件系统接口210<br />13.2　文件系统抽象层211<br />13.3　UNIX文件系统212<br />13.4　VFS 对象及其数据结构213<br />13.5　超级块对象214<br />13.6　超级块操作215<br />13.7　索引节点对象217<br />13.8　索引节点操作219<br />13.9　目录项对象222<br />13.9.1　目录项状态222<br />13.9.2　目录项缓存223<br />13.10　目录项操作224<br />13.11　文件对象225<br />13.12　文件操作226<br />13.13　和文件系统相关的数据结构230<br />13.14　和进程相关的数据结构232<br />13.15　小结233<br />第14章　块I/O层234<br />14.1　剖析一个块设备234<br />14.2　缓冲区和缓冲区头235<br />14.3　bio结构体237<br />14.3.1　I/O向量238<br />14.3.2　新老方法对比239<br />14.4　请求队列240<br />14.5　I/O调度程序240<br />14.5.1　I/O调度程序的工作241<br />14.5.2　Linus 电梯241<br />14.5.3　最终期限I/O调度程序242<br />14.5.4　预测I/O调度程序244<br />14.5.5　完全公正的排队I/O调度<br />程序244<br />14.5.6　空操作的I/O调度程序245<br />14.5.7　I/O调度程序的选择245<br />14.6　小结246<br />第15章　进程地址空间247<br />15.1　地址空间247<br />15.2　内存描述符248<br />15.2.1　分配内存描述符249<br />15.2.2　撤销内存描述符250<br />15.2.3　mm_struct 与内核线程250<br />15.3　虚拟内存区域251<br />15.3.1　VMA标志251<br />15.3.2　VMA 操作253<br />15.3.3　内存区域的树型结构和内存<br />区域的链表结构254<br />15.3.4　实际使用中的内存区域254<br />15.4　操作内存区域255<br />15.4.1　find_vma()256<br />15.4.2　find_vma_prev()257<br />15.4.3　find_vma_intersection()257<br />15.5　mmap()和do_mmap()：创建地址<br />区间258<br />15.6　munmap()和do_munmap()：删除<br />地址区间259<br />15.7　页表260<br />15.8　小结261<br />第16章　页高速缓存和页回写262<br />16.1　缓存手段262<br />16.1.1　写缓存262<br />16.1.2　缓存回收263<br />16.2　Linux 页高速缓存264<br />16.2.1　address_space对象264<br />16.2.2　address_space 操作266<br />16.2.3　基树267<br />16.2.4　以前的页散列表268<br />16.3　缓冲区高速缓存268<br />16.4　flusher线程268<br />16.4.1　膝上型计算机模式270<br />16.4.2　历史上的bdflush、kupdated 和<br />pdflush270<br />16.4.3　避免拥塞的方法：使用多线程271<br />16.5　小结271<br />第17章　设备与模块273<br />17.1　设备类型273<br />17.2　模块274<br />17.2.1　Hello，World274<br />17.2.2　构建模块275<br />17.2.3　安装模块277<br />17.2.4　产生模块依赖性277<br />17.2.5　载入模块278<br />17.2.6　管理配置选项279<br />17.2.7　模块参数280<br />17.2.8　导出符号表282<br />17.3　设备模型283<br />17.3.1　kobject283<br />17.3.2　ktype284<br />17.3.3　kset285<br />17.3.4　kobject、ktype和kset的<br />相互关系285<br />17.3.5　管理和操作kobject286<br />17.3.6　引用计数287<br />17.4　sysfs288<br />17.4.1　sysfs中添加和删除<br />kobject290<br />17.4.2　向sysfs中添加文件291<br />17.4.3　内核事件层293<br />17.5　小结294<br />第18章　调试295<br />18.1　准备开始295<br />18.2　内核中的bug296<br />18.3　通过打印来调试296<br />18.3.1　健壮性296<br />18.3.2　日志等级297<br />18.3.3　记录缓冲区298<br />18.3.4　syslogd和klogd298<br />18.3.5　从printf()到printk()的转换298<br />18.4　oops298<br />18.4.1　ksymoops300<br />18.4.2　kallsyms300<br />18.5　内核调试配置选项301<br />18.6　引发bug并打印信息301<br />18.7　神奇的系统请求键302<br />18.8　内核调试器的传奇303<br />18.8.1　gdb303<br />18.8.2　kgdb304<br />18.9　探测系统304<br />18.9.1　用UID作为选择条件304<br />18.9.2　使用条件变量305<br />18.9.3　使用统计量305<br />18.9.4　重复频率限制305<br />18.10　用二分查找法找出引发罪恶的<br />变更306<br />18.11　使用Git进行二分搜索307<br />18.12　当所有的努力都失败时：社区308<br />18.13　小结308<br />第19章　可移植性309<br />19.1　可移植操作系统309<br />19.2　Linux移植史310<br />19.3　字长和数据类型311<br />19.3.1　不透明类型313<br />19.3.2　指定数据类型314<br />19.3.3　长度明确的数据类型314<br />19.3.4　char型的符号问题315<br />19.4　数据对齐315<br />19.4.1　避免对齐引发的问题316<br />19.4.2　非标准类型的对齐316<br />19.4.3　结构体填补316<br />19.5　字节顺序318<br />19.6　时间319<br />19.7　页长度320<br />19.8　处理器排序320<br />19.9　SMP、内核抢占、高端<br />内存321<br />19.10　小结321<br />第20章　补丁、开发和社区322<br />20.1　社区322<br />20.2　Linux编码风格322<br />20.2.1　缩进323<br />20.2.2　switch 语句323<br />20.2.3　空格324<br />20.2.4　花括号325<br />20.2.5　每行代码的长度326<br />20.2.6　命名规范326&l;br />20.2.7　函数326<br />20.2.8　注释326<br />20.2.9　typedef327<br />20.2.10　多用现成的东西328<br />20.2.11　在源码中减少使用ifdef328<br />20.2.12　结构初始化328<br />20.2.13　代码的事后修正329<br />20.3　管理系统329<br />20.4　提交错误报告329<br />20.5　补丁330<br />20.5.1　创建补丁330<br />20.5.2　用Git创建补丁331<br />20.5.3　提交补丁331<br />20.6　小结332<br />