Linux内核设计与实现（第一章至第四章）

时间：May 4, 2017 分类：读书笔记

阅读本书的目的是为了更好的完成运维工作。(其实是我在去美团面试的时候，面试官问了我这么一个问题，在vi一个新文件，在文件中写入保存退出，Linux系统都执行了那些过程，越详细越好，我只是答了一点点，也希望通过阅读本书系统的了解一下一些底层的知识。)

本文只是阅读笔记，将博主认为重要的内容以博客的形式记录下来，笔者熟悉的就略过了，更详细的可以参考Linux内核设计与实现(第三版)。

Ps：计划搭建个云盘用于提供pdf下载。

第一章:Linux内核简介

历史

前身是贝尔实验室失败的Multies多用户操作系统；
1969年诞生，由Dennis Ritchie和Ken Thompson创建；
1973年Unix用C语言重写；
在余下的很多年里，开发者根据自己的需要增强了系统的功能；
1991年Linus Torvalds在使用Minix系统的时候，因为Minix许可协议不能轻易的修改和发布该系统源代码，在91年年底发布了Linux早期版本。

Linux强大的根本原因

简洁，提供几百个系统调用并且有一个非常明确的设计目的
所有东西都被当做文件对待(sockets就是个典型的例外)，这种抽象使对数据和设备的操作是用过一套相同的系统调用接口来进行，例如open()，read()，write()，lseek()和close()
使用C语言编写，在硬件体系架构中有很强的移植能力
进程创建迅速，使unix的程序把目标放到一次执行保质保量地完成一个任务上，并且有一个独特的fork()调用
提供了一套简单又稳定的进程通信原语，保证简单程序的方便组合去解决更加复杂的任务

4和5两点这种策略和机制的分离的设计理念，确保了Unix具备清晰的层次化结构

特点

支持多任务，多线程，虚拟内存，换页，动态链接和TCP/IP网络

应用领域

大到数百个CPU的集群，小到嵌入式设备的各种系统

Linux系统基础

内核，C库，工具集和系统基本工具(登录程序，shell和X windows等)

操作系统和内核的区别

功能

操作系统是指在整个系统中负责完成最基本功能和系统管理的部分，包括内核，设备驱动，启动引导程序，命令行shell或其他用户界面，基本的文件管理和系统工具。
内核是操作系统内在的核心，提供硬件设备管理，分配系统资源，响应中断，多进程分享处理器时间，进程地址空间内存管理，网络，进程间通信等系统服务程序。

空间

而用户在用户空间执行，它们只看到允许它们使用的部分系统资源，并且使用某些特定的系统功能，不能直接访问硬件，也不能访问内核划分给别人的内存范围，还有一些其他的使用限制。
内核独立于普通的应用程序，属于系统态，拥有保护的内存空间和访问硬件设备的所有权，系统态和被保护起来的内存空间统称为内核空间。

内核态和用户态交互

内核运行的时候，系统以内核态进入内核空间执行，而执行一个普通用户程序时，系统以用户态进入用户空间执行。应用程序与内核通过系统调用通信，例如调用库函数(比如C库函数)，由库函数通过系统调用界面，让内核代其完成各种不同的任务，当然也有一些库提供了系统调用不具备的许多功能，在那些较为复杂的函数中，调用内核的操作通常只是整个工作的一个步骤。例如printf()函数，提供了数据缓存和格式化等操作，而调用write()函数将数据写到控制台只是其中的一个动作。再例如open()函数，除了调用open()系统调用open()系统调用，几乎什么都不做。还有一些C库函数strcpy()根本就不直接调用系统级操作。

当一个应用程序执行一条系统调用，可以理解为内核再在带其运行，如果进一步解释，在这种情况下应用程序被称为通过系统调用在内核空间运行，而内核被称为运行于进程上下文中。这种交互关系——应用程序用过系统调用界面陷入内核——是应用程序完成其工作的基本方式。

中断机制

内核会负责管理系统的硬件设备，硬件架构中都提供了中断机制。

当硬件设备想和系统通信的时候，它首先要发送一个异步中断信号，去打断处理器的执行，继而打断内核的执行，中断通常对应一个中断号，内核通过这个中断号去查找对应的中断服务程序，并调用这个程序响应和处理中断。

最简的例子

敲击键盘
键盘控制器发送一个中断信号告知系统，键盘缓存区有数据到来，并将键盘输入存在键盘缓冲区
内核接收到这个中断号，调用相应的中断服务程序
服务程序处理键盘数据，并通知键盘控制器可以继续输入数据

为了保证同步，内核可以停用中止——即可以停止所有中断，也可以有选择地停止某个中断号的中断。

另外中断不在进程的上下文中执行，它们在一个与所有进程无关，专门的中断上下文中运行，这样才能保证中断服务程序能在第一时间响应和处理中断请求，并快速退出。

处理器在每个时间点的活动

概括一下就三类

运行于用户空间，执行用户进程
运行于内核空间，处于进程上下文，代表某个特定的进程执行
运行于内核空间，处于中断上下文，与任何进程无关，处理某个特定中断

包括cpu空闲时，内核就处于一个空进程，处于进程上下文，但运行在内核空间

书中配图

单内核和微内核

操作系统的内核主要是单内核和微内核，当然也有用于科研的外内核

单内核和微内核的区别

单内核设计简单，把内核整体上作为一个单独的大过程实现，运行在一个单独的地址空间，以单个静态二进制文件形式存放在磁盘中。因为所有内核服务都运行在一个内核地址空间，通信非常容易，并且内核可以直接调用函数，具有简单和性能高的特点。
微内核并不作为一个单独的大过程实现，相反被划分成了多个独立的过程，每个过程都保持独立运行在各自的地址空间，通过消息传递(IPC机制)进行内核通信，这样可以避免因为一个过程失效祸及另一个过程，也允许一个过程为了另一个过程换出。

单内核和微内核的应用

微内核因为IPC机制，在函数调用的过程中会占用较大的开销，涉及内核空间与用户空间的上下文切换，需要较长的消息传递周期，而单内核就没有系统调用的开销。

Windows NT内核和Mach(Mac OS X的组成部分)就是微内核，但是在新版本也不让微内核运行在用户空间。
Linux是一个单内核，但是也吸取了微内核的精华，模块化的设计，抢占式内核，支持内核线程以及动态装载内核模块，并避免了内核通信，让所有任务都运行在内核态。

Linux内核特点

支持动态加载内核模块，虽然是单内核
支持对称多处理(SMP)机制，与传统Unix不同
支持内核抢占，允许内核运行的任务优先执行，与传统Unix不同
内核不区分线程和一般进程，都是统一共享资源
支持设备类面向对象的设备模型，热插拔事件以及用户空间的设备文件系统
忽略了传统Unix的拙劣特性，例如STREAMS

内核版本特点

内核分为两种，稳定版本和处于开发中的版本。

版本命名机制，举例来说，版本号为2.6.32.1的内核，就是一个稳定版，内核主版本号为2，从版本号为6，修订版本号为32，稳定版本号为1

1.3系列的开发版稳定在2.0，而2.5系统的开发板稳定在2.6

第二章:从内核出发

内核源码树

目录	描述
arch	特定体系结构的源码
block	块设备I/O层
crypto	加密API
Documentation	内核源码文档
drivers	设备驱动程序
firmware	使用某些驱动程序而需要的设备固件
fs	VFS和各种文件系统
include	内核头文件
init	内核引导和初始化
ipc	进程间通信代码
kernel	像调度程序这样的核心子系统
lib	通用内核函数
mm	内存管理子系统和VM
net	网络子系统
samples	示例，示范代码
scripts	编译内核所用的脚本
security	Linux安全模块
sound	语音子系统
usr	早期用户空间代码(所谓的initramfs)
tools	在Linux开发中有用的工具
virt	虚拟化基础结构

还有一些文件

COPYING:内核许可证
CREDITS:开发内核代码的开发者列表
MAINTAINERS:维护者列表
Makefile:基本内核的Makefile

内核下载地址

https://cdn.kernel.org/pub/linux/kernel/

编译内核

内核可以根据自己需要的特定功能和驱动程序编译进内核，编译内核之前需要配置它，配置以CONFIG_FEATURE形式表示，其前缀为CONFIG。配置选项有二选一，yes或no，三选一，yes，no和module，module意味着该配置项被选定了。驱动程序一般为三选一。

module是作为一个模块，而yes是编译到主内核映像中。

配置选项可以是字符串或整数，这些选项并不控制编译过程，只是指定内核源码可以访问的值，一般以预处理宏的形式表示，比如，配置选项可以指定静态分配数组的大小。

更多编译内核可以参考12~15页，博主的主要目的是了解内核处理流程，更好的完成运维工作。

内核开发注意点

内核编程的时候不使用C库也不能访问标准的C头文件
内核编程的时候必须使用CNU C
内核编程缺乏像用户空间那样的内存保护机制
内核编程难以执行浮点运算，内核不能完美支持
内核给每个进程只有一个很小的定长堆栈
由于内存支持异步中断，抢占和SMP，因此必须时刻注意同步和并发

不使用C库的原因是为了速度和大小，对于内核来讲，C库太大并且效率低，不过大部分常用的C库函数都在内核中得到了实现。

提升性能的C语言扩展

内联函数

内联函数会在调用的位置展开，这么做可以消除函数调用和返回带来开销(寄存器存储和恢复)，不过代码会变长，占用更多的内存空间或占用更多的指令缓存，所以一般对时间要求高，本身长度比较短的函数定义为内联函数。

内联函数通过static作为关键字，并使用inline限定它。

内联函数必须在使用前定义好，否则编译器无法展开这个函数，编译的过程中不会为内联函数单独建立一个函数体。

内联汇编

在C函数中沟通过asm()嵌入汇编指令，用于偏近体系结构的底层或对执行时间要求严格的地方使用汇编语言。

分支声明

对于条件选择语句，gcc建了一条用于优化，在一个条件经常出现，或者该条件很少出现的时候，编译器可以根据这条指令对条件分支选择进行优化。内核把这条指令封装成了宏，比如likely()和unlikely()，unlily()用的更多一些。

例如认为error绝大多数时间都会为0

if (unlikely(error)) {
/* ... */
}

对条件选择语句优化的时候一定要搞清楚是否存在这么一个条件，在绝大多数成立，如果这个条件占压倒优势，性能就会提升，反之则会下降。

内核内存没有保护机制

访问非法内存地址或空指针会内核死掉
内核中内存不分页，每用掉一个字节，物理内存就少一个字节

同步和并发

内核容易产生竞争条件，但是内核要求能够并发访问共享数据，就要求内核有同步机制以保证不出现竞争条件。

Linux支持抢占，内核进程调度程序即兴对进程进行调度和重新调度，内核就必须和这些任务同步
Linux支持对称多处理器系统，没有保护，可能两个或以上处理器上的内核代码可能会访问共享的同一个资源
中断是异步的，优先级会高于正在执行的代码，中断和代码也可能访问共享的同一个资源
在抢占过程中，内核中执行的代码可能被另一代码抢占，从而导致几段代码访问共享的同一个资源

常用解决竞争的方法是自旋锁和信号量。

第三章:进程管理

进程和线程是Linux的抽象概念，本章介绍了Linux内核如何管理每个进程:如何被列举，如何创建，最终又如何消亡。

进程和线程

进程就是出于执行期的程序(目标码存放在某种存储介质上)，但是进程不局限于一段可执行程序的代码，还包含打开的文件，挂起的信号，内核内部数据，处理器状态，一个或多个具有内存映射的内存空间及一个或多个执行线程，存放全局变量的数据段。

线程是进程中的活动对象，每个线程都拥有独立的程序计数器，进程栈和一组进程寄存器。

内核调度对象

内核调度的对象是线程，而不是进程，传统情况，一个进程只有一个线程，现在一个进程多个线程。而操作系统的进程提供两种虚拟机制，虚拟处理器和虚拟内存，虽然实际上是很多进程共享一个处理，但是虚拟处理器给进程一种假象，让进程认为自己在独享处理器。

进程间和线程间资源共享

程序本身不是进程，一个程序可能包含两个或以上的进程，并且进程之间可以共享例如打开的文件，地址空间之类的资源。

一个进程的线程之间可以共享虚拟内存，但每个都拥有各自的虚拟处理器。

进程流程简述

进程的创建是内核通过父进程fork()函数调用系统的clone()，产生新的子进程，在调用结束后，fork()系统调用从内核返回两次，一次回到父进程，父进程恢复执行，另一次回到子进程，子进程开始执行。新的进程都是为了立即执行新的，不同的程序，接这调用exec()这组函数创建新的地址空间，并将程序载入到其中。程序退出通过exit()系统调用退出执行，结束进程并释放资源，父进程通过wait4()系统调用查询子进程是否终结，这使得进程拥有了等待特定进程执行完毕的能力，进程退出后被设置为僵死状态，直到父进程调用wait()或waitpid()为止。

下边会有单独介绍进程创建，执行和退出

进程描述符

进程描述符的描述

内核把进程的列表放在任务队列中，任务队列是一个双向循环链表。链表的每一项的类型为进程描述符(task_struct)。进程描述符中包含一个进程的所有信息，包含打开的文件，进程的地址空间，挂起的信号，进程的状态等更多信息

网上找到的双向循环链表

分配进程描述符

Linux通过slab分配task_struct，目的是对象复用和缓存着色，slab分配器动态生成task_struct，所以会在最低的内存地址(向下增长增长的栈为栈底，向上增长的栈为栈顶)创建一个新的结构struct thread_info。

thread_info结构在它的内存栈尾端分配，其中存放的是指向该任务实际task_struct指针。

进程描述符的存放

内核用过一个唯一的进程标识值或PID来标识每个进程，表示pid_t隐含类型，实际为一个int值，内核将其放入各自进程的进程描述符中，默认为32768(short int短整形的最大值)，这个最大值是系统允许存在的进程最大数量。

由于数值大的进程比数值小的进程迟运行，如果大型服务器需要特别多的进程，这个值越小，pid循环使用，转一圈转的越快，后来的进程比之前运行的进程PID小，就会比之前运行的进程优先运行，可通过修改/proc/sys/kernel/pid_max提高。

内核中大部分处理的代码都是直接通过task_struct进行的，访问任务通过current_thread_info()访问struct tread_info计算偏移量获得指向task_struct的指针，查找到task_struct。有些硬件体系可以拿出一个专门存放task的指针，用于加快访问速度，不过x86架构寄存器不富悦，Power的PC可以有这样一个寄存器。

进程状态

进程描述符中的state域描述了进程当前的状态，系统每个进程必然处于五种进程状态中的一种

TASK_RUNNING(运行)：进程是可执行的，或者正在执行状态，或者在运行队列中等待执行，这是进程在用户空间中执行的唯一可能的状态，这种状态也可以应用到内核空间中正在执行的进程。
TASK_INTERRUPTIBLE(可中断):进程正在睡眠(堵塞)，等待某些条件达成，内核会把该进程设置为运行状态，处于此状态的进程也会因为接收到信号而提前被唤醒并随时准备运行。
TASK_UNINTERRUPTIBLE(不可中断):除了接收到信号也不会被唤醒，或者准备投入运行外，这个状态与可打断状态相同。处于此状态的任务对信号不做响应，所以较之可中断的状态，使用的很少
TASK_TRACED:被其他进程追踪的进程，例如通过ptrace对调试程序进行跟踪。
TASK_STOPPED(停止):进程停止执行，进程没有投入运行，也不能运行。通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号。在调试期间接收到任何信号，都会使进程进入到这样的状态。

设置进程状态

内核调整进程的状态

set_task_state(task,state);     /* 将任务task的状态设置为state */

如果设置内存屏障来强制其他处理器做重新排序，一般只有在SMP系统中为必要。 set_current_state(state)和set_task_state(current,state)含义是等同。

进程上下文

可执行程序代码载入进程的地址空间执行，一般情况下程序在用户空间执行，当程序调用系统调用或者触发某种异常，程序会进入内核空间，除非有更高的优先级的进程需要执行由处理器调整，否则内核退出后程序恢复在用户空间继续及执行。

而系统调用或者触发某种异常对应着内核明确定义的接口系统调用和异常处理程序接口，进程只能通过这些接口访问内核。

进程家族树

所有进程都是PID为1的init进程的后代，系统启动的最后阶段内核启动init进程，读取系统的初始化脚本并执行其他相关程序，完成系统启动。除了init进程，每个进程都会有一个父进程，也会有零或多个子进程，有同一父进程的所有进程被称为兄弟，共享地址空间和打开文件等。

进程的关系放在一个进程描述符中，每个task_struct都包含一个父进程tast_struct的parent指针和一个children的子进程链表。而init的进程描述符是init_task静态分配的。

正是因为继承的体系，可以从系统的任何一个进程出发找到任意指定的其他进程。还有一种方法就是通过任务队列遍历系统所有进程，通过双向循环链表的向下查找next_task(task)和向上查找prev_task(task)实现，也可以for_each_process(task)访问整个队列，不过代价是很大的，不推荐。

进程创建

其他的操作系统提供产生进程的机制，在新的地址空间创建进程，读入可执行文件，而Linux系统将其分解为两个步骤，fork()和exec()。

fork()通过拷贝当前进程创建子进程，子进程与父进程区别在pid，ppid和某些资源(挂起信号等)，exec()负责读取可执行文件并将其载入地址空间开始运行。

fork()在拷贝过程中通过copy-on-write(写时拷贝)，在拷贝过程中不直接复制进程地址空间，而是子进程进和父进程共享拷贝，在需要写入的时候数据再进程复制，之前都是以只读方式共享，使地址空间上的页的拷贝被推迟到实际写入的时候进程。这样做一方面防止了直接拷贝的性能低下(why:说白了消耗时间长)，另一方面防止新进程可能会用不到这些拷贝(why:说白了还不一定有用)。

在fork()过程中实际的开销就是复制父进程的页表以及给子进程创建唯一进程描述符。在进程创建后一般都会马上运行一个可执行文件，写时拷贝可以加快进程的创建，避免了一些不必要的开销，优化了性能。

fork()

fork()是通过clone()实现的，在调用的过程中通过一系列指标来指明父，子进程需要共享的资源，相同的还有vofrk()和__clone()库函数都根据自身需要的参数标志去调用clone()，然后由clone()再去调用do_fork()去完成大量的工作，然后do_fork()调用copy_process()函数让程序开始运行。

copy_process()

调用dup_task_struct()为新进程创建内核，thread_info结构和task_struct进程描述符，此时子进程和父进程的描述符相同；
检查新的子进程创建后当前用户的总进程数没有超出当前用户分配的资源限制；
将子进程和父进程描述符进程区分，通过成员清0或设为初始值；
设置子进程的状态为TASK_UNINTERRUPTIBLE(进程正在睡眠)；
调用copy_flags()更新task_struct的flags成员，表明进程是否拥有超级用户权限的PF_SUPERPRIV标志被清0和没有调用exec()函数的PF_FORKNOEXEC标志被设置；
调用alloc_pid()为新进程分配有效PID；
根据传递给clone()参数标志，拷贝或共享打开的文件，文件系统信息，信号处理函数，进程地址空间和命名空间，这些一般都会被进程下所有线程共享；
最后返回一个指向子进程的指针

回到do_fork()函数，如果 copy_process()返回成功，新创建的子进程被唤醒并让其投入运行，然后是父进程，目的是在子进程启动会调用exec()函数，避免写时拷贝的额外开销，如果父进程先启动会开始向地址空间写入。

vfork()

vfork()与fork()不同的是，不拷贝父进程的页表项，子进程为父进程的一个单独的线程在它的地址空间运行，父进程被堵塞，直到子进程退出或执行exec()。这样就会出现如果子进程调用exec()失败的情况，所以内核实现的过程中不使用vfork()，详细的可以参考28页。

线程实现

线程是一种抽象概念，提供了同一程序共享内存地址空间运行，可以共享文件和其他资源，在多处理器系统上实现了真正的并行处理。

在Linux系统，内核中是没有线程的概念，把所有线程都当做进程来实现，线程被视为一个与其他进程共享某些资源的进程，每个线程也有属于自己的进程描述符。

而在其他操作系统例如Windows，在系统中提供了专门支持线程的机制——轻量级进程，线程被抽象为耗费较少资源，运行迅速的执行单元。

举例来讲，一个包含四个线程的进程，在Windows系统，会有一个包含四个线程的指针的进程描述符，负责描述地址空间，打开文件的共享资源，线程本身再去描述线程独占的资源，而Linux仅仅创建了四个task_struct结构，四个进程指定他们共享的某些资源，作者说这个高雅的做法，也对比其他操作系统创建时间短。

创建线程

线程的创建和普通的进程一样，都是在clone()的时候需要传递一些参数标志来指明需要共享的资源，资源不同而已。传递的参数标志决定了新的进程的行为方式和父子进程之间共享的资源种类

clone()参数(注TID为线程ID，TLS为Thread Local Storage) 参数标志 | 含义 ---|--- CLONE_FILES | 父子进程共享打开的文件 CLONE_FS | 父子进程共享文件系统信息
CLONE_IDLETASK | 将PID设置为0(只供idle进程使用) CLONE_NEWNS | 为子进程创建新的命名空间 CLONE_PARENT | 指定子进程与父进程拥有同一个父进程 CLONE_PTRACE | 继续调试子进程 CLONE_SETTID | 将TID回写至用户空间 CLONE_SETTLS | 为子进程创建新的TLS CLONE_SIGHAND | 父子进程共享信号处理函数及被阻断的信号 CLONE_SYSVSEM | 父子进程共享System V SEM_UNDO语义 CLONE_THREAD | 父子进程放入相同的线程组 CLONE_VFORK | 调用vfork()函数，所以父进程准备睡眠等待子进程将其唤醒
CLONE_UNTRACED | 防止跟踪进程在子进程上强制执行CLONE_PTRACE CLONE_STOP | 以TASK_STOPPED状态开始进程 CLONE_SETTLS | CLONE_CHILD_CLEARTID | CLONE_CHILD_SETTID | CLONE_PARENT_SETTID | CLONE_VM | 父子进程共享地址空间

创建fork() clone(SIGCHLD,0);
创建vfork() clone(CLONE_VFORK | CLONE_VM | SIGCHLD,0);
创建线程 clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGCHLD,0);

内核线程

内核在后台进行的操作就是通过内核线程完成。内核线程和普通的进程间的区别在于内核线程没有独立的地址空间，只在内核空间运行，从来不切换到用户空间，内核线程和普通进程一样，也可以被调度，也可以被抢占。

内核线程在系统启动的时候由内核线程创建，内核线程也只能由其他内核线程创建，内核是通过从kthreadadd内核进程中衍生出所有新的内核线程来处理的。由kthreadad进程调用clone()创建，运行threaddn()将其传递的参数为data，进程会被命名为namefmt，namefmt接收可变参数列表类似于printf()格式化参数。新创建的进程处于不可运行状态，需要调用wake_up_proccess()进行唤醒，但是也不会主动运行，需要kthread_run()来达到目的。运行直到调用do_exit()才会退出，或者内核其他部分调用kthread_stop()退出，传递给kthread_stop()的函数为kthreadcreate()函数返回task_struct结构的地址

进程终结

进程的终结是分为进程终止释放资源和进程描述符等内存删除分开执行

进程终止释放资源

进程终结的时候，内核会释放它所占用的所有资源并将进程终结告知父进程。进程终结需要进程调用exit()，当进程接收到它既不能处理也不能忽略信号或异常时，他还可能被动的终结，不管进程是如何终结，终结的任务都基本靠do_exit()来完成。

将task_struct中的标志成员设为PF_EXITING
调用del_timer_sync()删除任一内核定时器，确保没有定时器在排队，也没有定时器处理程序运行
如果BSD的进程记账功能开启，调用acct_update_integrals()来输出记账信息
调用exit_mm()函数释放进程占用的mm_struct，如果没有别的进程使用它们(地址空间没有被共享)就彻底释放
调用sem__exit()函数，如果进程排队等候IPC信号，则进程离开队列
调用exit_files()和exit_fs()，以分别递减文件描述符，文件系统数据的引用计数，如果引用计数为0，就代表没有进程使用相应的资源，可以释放该资源
将存放在task_struct的exit_code成员中的任务退出代码设置为由exit()提供的退出代码，接着去完成任何其他由内核机制规定的退出动作，退出代码存放在这里供父线程随时检索
调用exit_notify()向父进程发送信号，给子进程重新找养父，养父为线程组中的其他线程或init进程，并把进程状态exit_state设为EXIT_ZOMBIE
调用schedule()切换到新进程，EXIT_ZOMBIE的进程不会被调度，并且do_exit永不返回。

到此为止进程相关联的所有资源释放掉，进程也为不可运行，也没有地址空间，此时还占用内核栈，thread_info和tast_struct结构。

删除进程描述符

终结的进程占用内核栈，thread_info和tast_struct结构，需要父进程检索到这些信息，或者通知内核那些事无关信息后，进程的内存资源被释放归还给系统使用。

依赖的是wait()一族函数通过wait4()实现，标准动作为挂起调用它的进程，直到一个子进程退出，此时函数会返回该子进程的PID，此外调用该函数时提供的指针会包含子函数退出的代码。最终释放进程描述符时，release_task()会被调用，完成以下工作

调用__exit_signal()，该函数再调用_unhash_process()，该函数再调用detach_pid()从pidhash上删除该进程，同时也要从任务列表中删除该进程
_exit_signal()释放当前僵死进程所使用的所有剩余资源，并进行最终统计和记录
如果进程是线程组的最后一个进程，并且父进程已经死掉，那么release_task()就要通知其父进程的父进程
release_task()调用put_task_struct()释放进程内核栈和thread_info结构所占的页，并释放tast_struct所占的slab高速缓存

至此，进程描述符和所有进程独占的资源都被释放。

父进程在子进程之前退出

如果父进程在子进程之前退出，必须保证该子进程能找到一个父进程，否则子进程退出时就会永远处于一个僵死状态，白白占用内存，问题的解决方式就是在线程组内找一个线程作为父进程，如果不行就使用init做父进程。

过程是do_exit()调用exit_notify()，该函数会调用forget_original_parent()，而后者调用find_new_reaper()来寻找父进程，当找到父进程会遍历所有子进程为它们设置父进程，临时父进程被设定为调试进程，该进程被进行跟踪。

如果临时父进程退出，系统会为它和它同线程组的进程重新找一个新的父进程，进程找到新的父进程就不会出现驻留僵死状态的问题，init进程会例行调用wait()来检查其子进程，清除所有与其相关的僵死进程。会通过调用ptrace_exit_finish()同样进行新的寻找父进程，不过这次是为ptraced的子进程寻找父进程。遍历的会后是遍历的子进程链表和ptrace(追踪进程)链表，给其设置新的父进程。这两个链表的作用就是减少遍历带来的消耗。

第四章:进程调度

进程调度确保进程能有效的工作在一个内核子系统，决定那个进程进行运行，何时运行以及运行多久，进而充分使用系统资源。

简单的原理就是最大化利用处理器时间，原则是只要有可执行进程，就会有进程正在执行，如果可运行进程的数量超过处理器个数，就会有一个时刻有一些进程不能执行而是等待执行。

多任务

多任务是操作系统可以并发地交互执行多个进程，多任务使多个进程处于堵塞或者睡眠状态，尽管在内存中，不进行执行，利用内核阻塞自己，直到事件触发(键盘输入，网络数据，过一段时间等)，而只有少数处于可运行状态。

抢占多任务系统

多任务系统分为抢占式和非抢占式，抢占就是调度程序决定什么时候停止一个进程的运行，让其他进程得到执行机会，强制进程挂起的动作就是抢占，而进程被抢占之前能够运行的时间被提前预设好，被称为进程的时间片，时间片就是每个可执行进程处理器时间段，抢占的好处是避免个别进程独占系统资源。

现在很多的操作系统对程序运行都采用动态时间片计算的方式，并且引入了可配置的计算策略。而Linux使用了一种独一无二的‘公平’调度程序而并没有采用时间片的方式。

非抢占多任务系统

非抢占多任务系统除非进程自己主动停止运行，否则会一直执行，进程主动挂起被称为让步，理想状态系统通常会做出让步，不过也有缺点，调度程序无法规定每个进程的执行时间，一个不让步的进程会可能造成系统崩溃。

进程调度

最开始到2.4内核，Linux的调度程序非常简陋，不能胜任多可运行进程或多处理器环境
2.5内核，使用了O调度程序，因算法行为得名，解决了先前的不足，加入了静态时间片算法和针对每一处理器的运行队列，在处理数以十计的多处理器中支持很好，但是对响应时间敏感的程序——交互进程有不足
2.6内核引入了新的算法，例如反转楼梯最后期限调度算法(RSDL)，依照队列的理论，添加了公平调度，最后在2.6.23版本使用完全公平调度算法(CFS)

策略

策略决定调度程序何时让什么进程运行，进而优化处理器的使用时间

I/O消耗型和处理器消耗型

I/O消耗型进程是大部分时间都在提交I/O请求，这样的进程经常处于可运行状态，但是运行时间非常短，更多的时候是等待I/O请求时堵塞(I/O可以是键盘输入，网络I/O等)，对于用户图形化界面，就属于I/O密集型，即使不读写磁盘，也在等待鼠标或者键盘的用户交互操作。
处理器消耗型进程需要大量的时间来处理代码，除非被抢占会一直执行，因为没有大多I/O需求，所以从系统响应速度考虑，降低调度频率，进而延长运行时间。
即属于I/O消耗型又属于处理器消耗型，例如X Window服务调度策略会在进程响应时间和最大系统利用率(高吞吐量)之间寻求平衡，根据算法，决定那个进程进行运行，往往并不会保障低优先级会被公平对待。Linux为了保障交互式应用和桌面系统的性能，会对进程的响应做优化，更倾向于I/O消耗型进程，但也未忽略处理器消耗型进程。

进程优先级

进程优先级是根据进程的价值和其对处理器时间的需求来对进程分级，优先级高的先运行，优先级低的后运行，相同优先级的进程按照轮询方式进行调度，另外用户和进程都可以设置优先级来影响系统调度。

nice优先级

nice优先级默认为0，从-20到+19，nice值越高，优先级越低，在其他操作系统中获得的处理器时间越少，ps -el的N1一列就是nice值。在Mac OS X，进程nice代表了分配给进程的时间片的绝对值。

实时优先级

实时优先级是可以配置的，从0到99，数值越高，进程优先级越高，并且任何实时进程的优先级都高于普通进程，并且实时优先级和nice优先级无交集，可以用ps -eo state,uid,pid,ppid,rtprio,time,comm查看，位于RTPRIO列下，如果显示为‘-’则代表不是实时进程。

时间片

时间片是一个数值，表示进程在被抢占前所能持续运行的时间。调度策略需要规定一个默认时间片，如果时间片过长会导致系统对交互的响应表现欠佳，如果时间片太短就会明显增大进程切换带来的处理器消耗。而I/O消耗型不需要过大的时间片，而处理器消耗型希望时间片越长越好，这样高速缓存的命中率会更高。

Linux的CFS调度器并没有直接分配时间片给进程，而是将处理器的使用比划分给进程，这样进程获得的处理器时间与负载相关，当然也和nice值相关。在CFS调度器中，抢占时机取决于新的可运行程序消耗了多少处理器的使用比，如果比当前进程小，则新的进程抢占当前进程，立刻投入运行，否则推迟运行。

调度策略的活动

举个栗子，两个可运行进程，一个文字编辑程序和一个视频解码程序。文字编译是I/O消耗型，绝大多数时间都在等待用户输入(无论输入速度多快都没有处理速度快)，视频解码属于处理器消耗型，除了从磁盘读出原始数据流和最后把处理好的视频输出，程序所有的时间都在对数据进行视频解码，对于后者，用户几乎分辨不出也不关心它是立刻执行还是半秒后运行。

操作系统需要做到两点，一是系统给文本编辑程序更多的处理器时间，二是文本编辑器在有输入的时候被唤醒进而抢占视频解码程序，用来确保文本编辑器的交互性。

许多的操作系统，通过给文本编辑更多的时间片实现，Linux操作系统给两个程序分配处理器使用比，假设上只有这两个进程运行，这两个程序nice值相同，那么处理器的使用比都为50%，即平分处理器时间，但是由于文本编辑的处理器使用时间肯定不会到50%，那么视频解码进程的处理器时间有机会超过50%，而当文本编辑进程在用户输入的情况下被唤醒，根据CFS策略，文本编辑进程比视频解码进程处理器使用时间短，但是使用比是相同的，文本编辑进程就会立刻抢占视频解码进程，进而运行起来，处理完用户请求后进入睡眠状态等待用户下一次输入。

Linux调度算法

调度器类

Linux的调度器以模块的方式提供，允许不同类型的进程针对性选择调度算法，完全公平调度(CFS)是一个针对普通进程的调度类，在kernel/sched_fair.c中。

进程调度

现代进程调度

现代进程调度器有两个概念，分别是时间片和进程优先级，进程启动的时候会有一个默认的时间片，更高优先级的进程将运行的更加频繁，而且有更多的时间片

Unix进程调度

Unix系统的进程调度在优先级以nice值的形式输出给用户空间，但是有以下问题:

nice映射到时间片，nice单位值以绝对值对应到处理器的时间片，这样会产生进程切换频繁，例如nice值0的进程分配到100ms，nice值19的进程分配到5ms，就会有105ms两次上下文切换。而nice值相同，就会都为5ms，就会在10ms内进行两次上下文切换。
相对nice值，例如nice值0的进程分配到100ms，nice值1的进程分配到95ms，时间几乎一样，而nice为18和19，时间分别是10ms和5ms，前者是后者的两倍
nice值到时间片的映射，分配绝对时间片，必须绝对时间片为定时器节拍的整数倍，也就是10ms和1ms的倍数，这样最小的时间片必然是定时器的整数倍，如果出现1和7的优先级，这个时间片的比例为19:13
基于优先级的调度器为了优化交互任务，会对新唤醒的进程提高优先级，即使时间片用尽，虽然可以提升交互性能，但是也可能造成打破公平规则，损害其他进程的情况。

Linux进程调度

CFS公平调度允许每个进程运行一段时间，循环轮转，选择运行最少的进程作为一下个运行的进程，而不是直接分配时间片，可以更好的保证系统的性能。但是会有一个目标延迟，假定目标延迟为20ms，2个相同优先级的进程，被抢占前运行10ms，但是如果更多呢，就会趋近于0，所以CFS引入了每个进程的时间底线，最小粒度，默认为1ms。举个栗子，一个nice值为0的进程，另一个nice值为5的进程，进程nice值为5的权重为默认的1/3，如果目标延迟为20ms，这两个进程就会获得15ms和5ms的处理器，如果是nice值为10和15的进程，也是15ms和5ms，是通过相对值来影响处理器时间分配。

调度实现

关注点在时间记账，进程选择，调度器入口，睡眠和唤醒

时间记账

时间记账是通过给进程的时间片在每次时钟节拍，节拍周期减1实现，直到减少为0，就会被另一个未被减少为0的进程抢占

调度器实体结构

而CFS没有时间片的概念，使用调度器实体结构来追踪进程运行记账，调度器实体结构作为一个名为se的成员变量，嵌入进程描述符。

虚拟实时

vruntime变量存放进程的虚拟运行时间，时间计算了所有可运行进程总数的标准化(经过加权)，虚拟时间以ns为单位。CFS使用vruntime记录了一个进程运行了多久以及还能运行多久。

update_curr()函数实现了记账功能，该函数计算了当前进程的执行时间，并且将其存放在delta_exec中，将运行时间传递给了__update_curr()，由__update_curr()根据当前可运行进程的总数对运行时间进行加权计算，最终上述权重值与当前进程的vruntime相加。__update_curr()是由系统定时器周期性调用，无论进程处于运行状态还是堵塞不可运行状态，vruntime都可以准确测量给定进程的运行时间，并且哪一个是下一个被运行的进程。

进程选择

CFS调度选择下一个运行进程时，会选择一个具有最小vruntime的进程，原理是使用红黑树(在Linux中为rbtree，自平衡二叉搜索树)来组织可运行进程队列，利用其快速寻找最小vruntime值的进程(why:可以理解为最需要立即响应执行的进程)。

红黑树是一种以树节点形式存储的数据，这些数据都会对应一个键值，可以通过键值来快速检索节点上的数据，通过键值检索到对应节点的速度与树的节点规模成指数比关系。

挑选下一个任务

假设红黑树存储了系统中所有可运行进程，节点键值就是可运行进程的虚拟运行时间，CFS调度时选取最小vruntime的进程，对应的就是树中最左侧的叶子节点，意味着顺着左边的节点一直向下找就可以找到，实现这一过程的函数为__pick_next_entity()，此函数不会遍历最左的叶子节点，这个值已经缓存在rb_leftmost中，如果为null，那么就代表没有可以运行的进程，CFS调度会选择idle任务进行运行。

向树中加入进程

向树中加入进程是在进程变为可运行状态或者是通过fork()调用第一次创建进程时，通过的是enqueue_entity()函数实现，该函数调用update_curr()更新运行时间，再调用__enqueue_entity()进行插入到红黑树中，并维护缓存树的最左叶子节点(如果执行是左分支，leftmost为1，一点往右分支就会变为0，如果节点不存在，通过rb_link_node()会在父节点创建分支，最后rb_insert_color()函数更新树的自平衡相关属性)

从树中删除进程

删除动作发生在进程堵塞或者结束运行，通过调用dequeue_entity()实现，该函数调用update_curr()更新运行时间，再调用__dequeue_entity()在红黑树中删除。删除只需要使用rbtree中的rb_erase()函数，更新rb_leftmost缓存，如果删除的是最左节点，会调用rb_next()遍历，找到新的最左节点。

调度器入口

调度器的入口为schedule()，定义在kernel/sched.c。内核其他部分用于调用进程调度器的入口，选择那些进程可以运行，何时投入运行，这个过程需要schedule()通过与调度类关联实现。调度类首先要有自己的可运行队列，schedule()函数通过调用pick_next_task()函数以优先级为序，由高到低，检查每个调度类，从最高优先级的调度类中选择最高优先级的进程。

CFS是普通进程的调度类，而系统绝大多数都是普通进程，所以如果可运行进程都为普通进程，就可以快速的选择下一个进程了。

pick_next_task()的核心是for循环，遍历调度类，每一个调度类都实现了pick_next_task()，返回下一个可运行进程的指针(没有就会返回null)，然后在第一个返回非null值的类中选择下一个可运行进程，进而调用pick_next_entity()函数

睡眠与唤醒

休眠(被堵塞)的进程处于一个特殊的不可运行的状态，进入这种状态的情况有很多种，但是都肯定是等待一些事件，这些事件可以是一段时间从文件I/O读取数据(执行read()操作)或某些硬件事件(等待获取键盘输入)，也可能是尝试获取一个被占用的内核信号量时被迫进入休眠，前两者内核的操作都是相同的，进程把自己标记为休眠状态，从可执行红黑树中移除，放入等待队列，然后调用schdule()选择和执行其他进程。唤醒会休眠相反，进程把自己标记为可执行状态，然后从等待队列移动到可执行红黑树中。

等待队列

休眠通过一个被称为等待队列的简单链表，内核用wake_queue_head_t代表等待队列，这个队列可以通过DECLARE_WAITQUEUE()静态创建，也可以通过init_waitqueue_head()创建，进程会把自己的状态设置为不可执行的休眠状态并放入等待队列，与等待队列相关的事件发生后，队列上的进程会被唤醒。

等待条件发生的接口如果存在竞争，就会可能在判断条件之后，进程缺还在休眠，并且无限期休眠下去。

进程加入等待队列的流程

调用宏DEFINE_WAIT()创建一个等待的队列的项
调用add_wait_queue()把自己加入到队列中，该队列会在进程等待的条件满足的情况下唤醒，事件发生对队列执行wake_up()
调用prepare_to_wait()将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，而且必要的情况下会将进程加入到等待队列。
状态为TASK_INTERRUPTIBLE的进程由信号唤醒进程，此时为伪唤醒
当进程被伪唤醒，会再次检查条件是否为真，如果为真退出循环，如果为假，再次调用schedule
条件满足后进程将自己设置为TASK_RUNNING并调用finish_wait()方法将自己移出等待队列

如果在进程进入休眠之前就已经满足休眠条件，就会退出循环，进程不会存在错误的进入休眠倾向。

唤醒

唤醒操作是通过函数wake_up()进行，会唤醒指定的等待队列上的所有进程。wake_up()函数调用函数try_to_wake_up()将进程设置为TASK_RUNNING状态，然后它在调用enqueue_task()将进程放入红黑树中，如果被唤醒的进程优先级比当前执行的进程优先级高，还会被设置为need_resched标志。

例如当磁盘数据到来，VFS负责对等待队列调用wake_up()，以便唤醒队列中等待这些数据的进程。

抢占和上下文切换

上下文切换

上下文切换是一个可执行进程切换到另一个可执行进程，由 context_switch()函数负责处理，当一个新进程准备投入运行，就会调用该函数。

该函数完成了两项任务：

调用switch_mm()，把虚拟内存从上一个进程映射切换到新的进程中。
调用switch_to()，把处理器状态从上一个进程切换到新的进程处理器状态，包括保存，恢复栈信息和寄存器信息以及任何相关的状态信息

内核需要知道何时调用schedule()，如果由用户调用schedule()，可能会造成进程一直执行下去，所以内核提供了need_resched标志来标记进程是否需要重新执行调度。操作need_resched的函数有set_tsk_need_resched()设置标记，clear_tsk_need_resched()清除标记，need_resched()检查标志。

当进程被抢占的时候，schedule_tick()就会设置该标志，当一个高优先级程序进入可执行状态的时候也会通过try_to_wake_up()也会设置这个标志，然后内核检查到该标记后，调用schedule()来调度进程。返回用户空间和中断返回的时候，内核也会检查need_resched标志。所以每个进程都会有个need_resched标志，因为访问进程描述符比访问一个全局变量快，而在2.2版本为一个全局变量，2.2到2.4在task_struct中，2.6版本则直接放到thread_info结构体，用一个特殊的标志变量来表示。

用户抢占

内核即将返回用户空间的时候，如果被设置了need_resched标志，会调用schedule()，此时会发生用户抢占。此时内核返回用户空间，可以继续执行当前进程，也可以选择一个新的进程去执行，当然中断处理完也会，注意，只是调用schedule()并不一定进行进程切换。

所以用户抢占发生在系统调用返回用户空间和中断处理返回用户空间

内核抢占

不支持内核抢占的系统中，如果有内核级进程执行，就会一定等内核级进程执行完(或者返回用户空间)，调度程序才会执行调度，而Linux作为完整支持内核抢占，只要在重新调度时安全的时候就可以抢占正在执行的内核任务(注：有些内核代码禁止被抢占)。

安全的定义为进程没有锁，就可以进程抢占，因为没有锁代表正在执行的代码就是可以重新导入的，所以具备继续(或重新)执行的条件。锁对应的为每个进程的thread_info引入preempt_count计数器，期初值为0，代表没有锁可以被内核抢占，使用锁的时候该值加1，释放锁的时候该值减1(那是否意味着可以有多个锁)。中断返回内核空间，内核也会检查当前进程的need_resched和preempt_count，如果被设置且后者为0，则中断可以抢占运行进程，如果不为0则为不安全就不进行抢占。另一方面，在释放锁的时候也会检查need_resched是否被设置，如果被设置，会通过调度程序。

所以内核抢占发生在中断处理返回内核空间，内核代码具备可抢占性，内核显式调用schedule()和内核任务堵塞(调用schedule())

实时调度策略

普通的非实时调度策略为SCHED_NORMAL，Linux提供了SCHED_FIFO和SCHED_RR两个实时调度策略，这些实时策略并不完全被CFS调度器管理，而被一个特殊的实时调度器管理。

SCHED_FIFO为先进先出的简单调度算法，不使用时间片，处于可运行状态的SCHED_FIFO进程会比任何一个SCHED_NORMAL进程优先调度，并且会一直执行，只有更高优先级的SCHED_FIFO进程或SCHED_RR进程才会进行抢占，如果是相同优先级的SCHED_FIFO进程，会轮流执行，但是只有在它们放弃使用处理器才会退出。

SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR会在耗尽分配的时间后就不再执行，可以理解为有时间片的SCHED_FIFO。

当然内核不能满足实时调度策略。

调度相关系统调用

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

实时优先级，是0~139，0~99是对应实时调度策略，而100~139对应nice值的-20到+19

sched_setscheduler()和sched_getscheduler()实现是参数检查，初始化和清理构成，例如读写tast_struct的policy和rt_priority。sched_setparam()和sched_getparam()获取分装在sched_param结构体中的rt_priority，nice()会调用set_user_nice()函数设置task_struct的static_prio好prio值

处理器绑定的系统调用

Linux通过调度策略做了软的处理器亲和，尽量使进程在一个处理器上运行，强制的亲和性保存在task_struct的cpus_allowed这个位掩码标志中，对应一个系统可用的处理器，子进程会继承父进程运行在父进程绑定的处理器上运行。

放弃处理器时间

通过sched_yield()系统调用，提供了进程显式将处理器时间让其他等待执行的进程，原理是将进程从活动队列移动到过期队列。

火眼征信大数据工程师闫大佬