深入理解Linux内核进程的创建、调度和终止

在Linux 操作系统的神秘世界里，进程就像是一个个充满活力的小生命，它们不断地诞生、成长、工作，最终走向终止。你可以把 Linux 内核想象成一个庞大而有序的城市，进程则是城市里形形色色的居民和组织，它们有着各自的任务和使命，在这个城市里穿梭忙碌。

进程的创建，如同新生命的诞生，为系统带来了新的活力和任务；进程的调度，就像是城市交通的指挥者，合理地分配时间和资源，确保每个进程都能有序地运行；而进程的终止，则是生命的落幕，释放出资源，让系统得以持续高效地运转。今天，就让我们一起深入 Linux 内核进程的世界，揭开它们创建、调度和终止的神秘面纱，探寻其中的奥秘和乐趣 。

一、Linux进程的概念

进程（Process）是指计算机中已运行的程序，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。进程是程序真正运行的实例，若干进程可能与同一个程序相关，且每个进程皆可以同步或异步的方式独立运行。

进程的概念主要有两点：第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用的指令和本地变量。第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时（操作系统执行之），它才能成为一个活动的实体，我们称其为进程。

1.1描述进程PCB

进程：资源的封装单位，linux用一个PCB来描述进程，即task_struct， 其包含mm,fs,files,signal…

将分区/dev/sda5挂载到/mnt/a，调用chroot，改变root目录，当前进程下的文件b.txt即位于当前进程的根目录。

总用量 0

Linux总的PID是有限的，用完PID

每个用户的PID也是有限的

1.2 task_ struct内容分类

在进程执行时，任意给定一个时间，进程都可以唯一的被表征为以下元素：

1.3Linux进程的组织方式

linux里的多个进程，其实就是管理多个task_struct，那他们是怎么组织联系的呢？

组织task_struct的数据结构：

用三种数据结构来管理task_struct，以空间换时间。父进程监控子进程，linux总是白发人送黑发人。父进程通过wait，读取task_struct的退出码，得知进程死亡原因。并且清理子进程尸体。

Android/或者服务器，都会用由父进程监控子进程状态，适时重启等；

1.4进程的状态和转换

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化（一个进程会经历若干种不同状态）。通常进程有以下五种状态，前三种是进程的基本状态。

注意区别就绪状态和等待状态：就绪状态是指进程仅缺少处理机，只要获得处理机资源就立即执行；而等待状态是指进程需要其他资源（除了处理机）或等待某一事件。之所以把处理机和其他资源划分开，是因为在分时系统的时间片轮转机制中，每个进程分到的时间片是若干毫秒。

也就是说，进程得到处理机的时间很短且非常频繁，进程在运行过程中实际上是频繁地转换到就绪状态的；而其他资源（如外设）的使用和分配或者某一事件的发生（如I/O操作的完成）对应的时间相对来说很长，进程转换到等待状态的次数也相对较少。这样来看，就绪状态和等待状态是进程生命周期中两个完全不同的状态，很显然需要加以区分。

二、Linux进程诞生

2.1进程创建方式

在 Linux 系统中，主要有三种方式可以创建新的进程，分别是fork、vfork和clone系统调用 。这三种方式就像是三把不同的钥匙，虽然都能打开进程创建的大门，但各自有着独特的开启方式和适用场景。

fork创建一个新进程，也需要创建task_struct所有资源；实际上创建一个新进程之初，子进程完全拷贝父进程资源，如下图示：

比如fs结构体：

子进程会拷贝一份fs_struct，

pwd路径和root路径与父进程相同，子进程修改当前路径，就会修改其p2_fs->pwd值；父进程修改当前路径，修改p1_fs->pwd;

2.2fork 函数原理

fork函数的原型非常简洁：pid_t fork(void); 。这个函数就像是一个神奇的开关，当它被调用时，会在操作系统中引发一系列奇妙的变化。它会创建一个新的进程，这个新进程就是子进程，而调用fork的进程则是父进程。

从实现原理上看，fork函数会复制父进程的几乎所有资源，包括虚拟地址空间、堆栈、打开的文件描述符等。在虚拟地址空间方面，父子进程各自拥有自己独立的虚拟地址空间，但它们共享代码段（因为代码段通常是只读的，不需要为每个进程单独复制一份）。这就好比父子俩住在各自的房子里（虚拟地址空间），但他们共享同一个图书馆（代码段） 。

在早期的 Unix 系统中，fork创建子进程时会直接复制父进程的整个地址空间，这会导致大量的内存拷贝操作，效率非常低下。后来引入了写时拷贝（Copy-On-Write，COW）技术，大大提高了fork的效率。写时拷贝技术的原理是，在fork创建子进程时，并不立即复制父进程的地址空间，而是让父子进程共享相同的物理内存页面。只有当其中一个进程试图修改共享的内存页面时，系统才会为修改的页面创建一个副本，分别分配给父子进程。这就好比父子俩一开始共享同一本书（物理内存页面），当其中一个人想要在书上做笔记（修改内存页面）时，才会复制一本新的书给他 。

其他资源大体与fs类似，最复杂的是mm拷贝，需借助MMU来完成拷贝；

即写时拷贝技术：

写时拷贝技术带来了很多好处。首先，它节省了内存开销，因为在大多数情况下，父子进程在fork之后并不会立即修改共享的内存，所以不需要一开始就复制大量的内存。其次，它提高了进程创建的效率，减少了fork操作的时间开销 。

第一阶段：只有一个进程P1，数据段可读可写：

第二阶段，调用fork之后创建子进程P2，P2完全拷贝一份P1的mm_struct，其指针指向相同地址，即P1/P2虚拟地址，物理地址完全相同，但该内存的页表地址变为只读；

第三阶段：当P2改写data时，子进程改写只读内存，会引起内存缺页中断，在ISR中申请一片新内存，通常是4K，把P1进程的data拷贝到这4K新内存。再修改页表，改变虚实地址转换关系，使物理地址指向新申请的4K，这样子进程P2就得到新的4K内存，并修改权限为可读写，然后从中断返回到P2进程写data才会成功。整个过程虚拟地址不变，对应用程序员来说，感觉不到地址变化。

谁先写，谁申请新物理内存；Data=20；这句代码经过了赋值无写权限，引起缺页中断，申请内存，修改页表，拷贝数据…回到data=20再次赋值，所以整个执行时间会很长。

这就是linux中的写时拷贝技术(copy on write), 谁先写谁申请新内存，没有优先顺序；cow依赖硬件MMU实现，没有MMU的系统就没法实现cow，也就不支持fork函数,只有vfork;

2.3vfork 函数原理

vfork函数的原型同样简单：pid_t vfork(void); 。它与fork函数有着明显的区别。vfork创建的子进程与父进程共享地址空间，这意味着子进程完全运行在父进程的地址空间上，如果子进程修改了某个变量，那么父进程中的这个变量也会被改变。而且，vfork保证子进程先运行，在子进程调用exec或exit函数之前，父进程会被阻塞，处于暂停状态 。

这种特性使得vfork适用于一些特定的场景，比如子进程需要立即执行另一个程序的情况。因为子进程共享父进程的地址空间，所以在创建子进程时不需要复制大量的内存，从而节省了时间和资源。例如，当我们需要启动一个新的程序时，可以使用vfork创建子进程，然后在子进程中调用exec函数来加载新的程序，这样可以快速地启动新程序，而不会浪费过多的资源 。

不过，使用vfork也需要特别小心。由于子进程和父进程共享地址空间，如果子进程在调用exec或exit之前对共享的变量进行了修改，可能会影响到父进程的正常运行。所以，在使用vfork时，一定要确保子进程尽快调用exec或exit函数，以避免出现意想不到的问题 。

2.4clone 函数原理

clone函数的原型相对复杂一些：int clone(int (*fn)(void *), void *child_stack, int flags, void *arg); 。它接受多个参数，这些参数赋予了clone函数强大的灵活性。

fn参数是一个函数指针，指向新进程开始执行的函数，就像是为新进程设定了一个起点。child_stack参数指定了新进程的用户态栈指针，为新进程提供了一个独立的堆栈空间 。

flags参数是一个标志位，它决定了新进程如何继承父进程的资源。通过设置不同的标志位，可以实现不同的资源共享和进程创建方式。比如，CLONE_VM标志表示新进程与父进程共享内存描述符和所有的页表，这样它们就可以共享内存空间；CLONE_FS标志表示共享文件系统，包括根目录、当前目录和文件权限掩码等；CLONE_FILES标志表示共享打开的文件描述符，使得父子进程可以访问相同的文件 。

arg参数是传递给fn函数的参数，就像是给新进程传递了一份 “行李”，让它在开始执行时可以使用 。

clone函数创建进程的独特之处在于它可以根据用户的需求，精细地控制新进程对父进程资源的继承方式，既可以创建完全独立的进程，也可以创建共享部分资源的轻量级进程（线程）。这种灵活性使得clone函数在很多场景下都能发挥重要作用，比如在实现多线程库时，就可以利用clone函数来创建共享内存和文件描述符的轻量级进程，模拟线程的行为 。

Linux中创建进程(fork，vfork)和线程(pthread_create)，在内核都是调用do_fork()–>clone()，参数clone_flags标记表明哪些资源是需要克隆的，创建线程时，所有资源都克隆；

从调度的角度理解线程，从资源角度来理解进程，内核里只要是task_struct，就可以被调度；linux中的线程又叫轻量级进程lwp;

2.5幕后英雄：do_fork 和 copy_process

在进程创建的过程中，do_fork函数是真正的核心。它就像是一场精彩演出背后的导演，负责协调和安排进程创建的各个环节 。do_fork函数定义在 Linux 内核的kernel/fork.c文件中，它接受多个参数，包括clone_flags（克隆标志）、stack_start（栈起始地址）、regs（寄存器值）和stack_size（栈大小）等。这些参数就像是导演手中的剧本和道具清单，决定了新进程的各种特性和资源分配 。

do_fork函数主要完成以下几个关键任务：首先，它会根据clone_flags标志来检查创建进程的合法性，确保满足各种条件和限制。然后，它会调用copy_process函数来创建新进程的描述符和其他内核数据结构 。在创建过程中，它会为新进程分配一个唯一的进程 ID（PID），这个 PID 就像是新进程的身份证，用于在系统中唯一标识这个进程 。

copy_process函数则是do_fork函数的得力助手，它负责具体创建新进程的描述符和其他内核数据结构。它就像是一个勤劳的工匠，精心打造新进程所需的各种 “零件” 。copy_process函数首先会调用dup_task_struct函数复制当前进程的task_struct结构体，这个结构体是进程描述符，包含了进程的各种信息，如进程状态、优先级、打开的文件描述符等 。

接着copy_process函数会检查新进程的资源限制，确保不会超过系统的限制。然后，它会初始化新进程的各种属性，如设置进程的状态为可运行状态（TASK_RUNNING），初始化进程的信号处理函数、文件系统信息等 。在初始化过程中，它会根据clone_flags标志来决定新进程如何继承父进程的资源，是完全复制还是共享部分资源 。

最后，copy_process函数会调用copy_thread函数来初始化子进程的内核栈，为子进程的执行做好准备。通过do_fork和copy_process函数的协同工作，一个新的进程就诞生了，它带着自己的使命和资源，开始在 Linux 系统这个大舞台上展现自己的活力 。

三、Linux进程调度

3.1调度策略

在 Linux 的进程调度舞台上，有多种调度策略可供选择，每种策略都有其独特的特点和适用场景，就像是不同风格的舞蹈，在不同的音乐节奏下展现出各自的魅力 。

首先是SCHED_OTHER，它是默认的分时调度策略，适用于大多数普通应用程序。在这种策略下，系统会根据进程的nice值（取值范围为 - 20 到 19，数值越小优先级越高）来分配 CPU 时间。nice值就像是进程的 “好感度”，好感度越高（nice值越小）的进程，获得 CPU 时间的机会就越大 。例如，一个普通的文本编辑程序，它对实时性要求不高，就可以采用SCHED_OTHER调度策略，让系统合理地分配 CPU 时间，保证它能正常运行 。

SCHED_FIFO是实时调度策略中的先进先出策略，适用于对时间要求严格、需要立即执行的实时任务 。一旦一个SCHED_FIFO类型的进程获得了 CPU，它就会一直运行下去，直到它主动放弃 CPU（比如因为等待 I/O 操作而阻塞）或者被更高优先级的进程抢占 。这就好比一场紧张的赛车比赛，一旦赛车驶入赛道，就会一直飞驰，直到遇到特殊情况才会停下来 。比如，工业控制系统中的一些实时控制任务，需要对外部设备的信号做出快速响应，就可以使用SCHED_FIFO策略，确保任务能及时执行，避免因延迟而导致生产事故 。

SCHED_RR也是实时调度策略，它是时间片轮转调度策略 。与SCHED_FIFO不同的是，SCHED_RR为每个进程分配一个固定的时间片，当进程的时间片用完后，它会被放到就绪队列的末尾，等待下一次调度 。这就像是一场接力赛跑，每个选手都有自己的固定跑步时间，时间一到就把接力棒交给下一位选手 。对于一些对响应时间要求严格且执行时间较短的实时任务，比如多媒体播放中的音频和视频解码任务，使用SCHED_RR策略可以保证每个任务都能得到及时处理，避免出现音频卡顿或视频掉帧的情况 。

在优先级关系上，实时进程（采用SCHED_FIFO和SCHED_RR策略）的优先级高于普通进程（采用SCHED_OTHER策略） 。这意味着当有实时进程就绪时，系统会优先调度实时进程，确保它们能及时运行，而普通进程则需要等待实时进程执行完毕或者主动放弃 CPU 后才有机会运行 。

3.2调度算法

Linux 内核中，完全公平调度器（CFS）是进程调度的核心算法之一，它的设计目标是实现所有进程公平分享 CPU 资源 。CFS 就像是一位公正的裁判，努力让每个进程都能在 CPU 这个赛场上获得公平的比赛时间 。

CFS 的工作原理基于虚拟运行时间（vruntime） 。每个进程都有一个vruntime值，它表示进程的虚拟运行时间 。vruntime的计算方式为：vruntime = 实际运行时间 × 1024 / 进程权重 。这里的进程权重由进程的nice值决定，nice值越小（优先级越高），权重越大 。例如，一个nice值为 - 5 的进程，它的权重会比nice值为 5 的进程大，在相同的实际运行时间下，它的vruntime增长速度会更慢 。

CFS 使用红黑树来存储可运行进程，以vruntime为键值 。每次调度时，CFS 会选择红黑树中最左侧节点（即vruntime最小的进程）运行 。这就好比在一场比赛中，裁判总是选择那些 “跑得最慢”（vruntime最小）的选手先上场，让每个选手都有机会展示自己 。通过这种方式，CFS 保证了每个进程都能公平地获得 CPU 时间，避免了某些进程长时间占用 CPU 而导致其他进程饥饿的情况 。

实时调度策略主要包括SCHED_FIFO和SCHED_RR，它们适用于对时间要求严格的实时任务 。实时调度策略的特点是优先级较高，能够确保实时任务在规定的时间内完成 。对于SCHED_FIFO策略的任务，一旦获得 CPU 就会一直运行，直到主动放弃或被更高优先级任务抢占；而SCHED_RR策略的任务则是按照时间片轮转的方式运行，每个任务在自己的时间片内运行，时间片用完后会被放到就绪队列末尾 。

这些实时调度策略在工业控制、航空航天等对实时性要求极高的领域有着广泛的应用，比如在航空航天领域，飞行器的飞行控制任务需要实时处理各种传感器数据，对时间的准确性要求极高，使用实时调度策略可以确保这些任务能够及时、准确地执行，保障飞行器的安全飞行 。

3.3调度时机

进程调度的时机就像是一场音乐会中节奏的转换点，把握得恰到好处才能让整个演出流畅进行 。在 Linux 系统中，进程调度会在多种情况下发生 ：

当系统调用返回时，是一个常见的调度时机 。系统调用就像是进程向操作系统发出的服务请求，当请求处理完成返回时，系统会检查是否有更合适的进程需要运行 。比如，一个进程调用read系统调用来读取文件数据，在读取完成返回后，系统可能会发现有其他进程的优先级更高或者等待时间更长，这时就会进行进程调度，让更合适的进程获得 CPU 。

中断处理完成后也会触发进程调度 。中断就像是紧急事件的通知，当硬件设备（如键盘、鼠标、网卡等）产生中断时，操作系统会暂停当前进程的执行，去处理中断事件 。当中断处理完成后，系统会重新评估当前的进程状态，决定是否进行进程调度 。例如，当用户按下键盘时，会产生键盘中断，操作系统会暂停当前正在运行的进程，去处理键盘输入事件，处理完成后，再根据情况决定是否调度其他进程 。

进程主动放弃 CPU 也是调度的时机之一 。有些进程在执行过程中，可能会因为等待某些资源（如等待其他进程发送信号、等待 I/O 操作完成等）而主动调用schedule函数放弃 CPU 。比如，一个进程需要等待另一个进程完成某项任务后才能继续执行，它就会主动调用schedule函数，将 CPU 让给其他可运行的进程，直到等待的条件满足后再重新竞争 CPU 。

另外，当进程的时间片用完时，也会进行进程调度 。在采用时间片轮转调度策略（如SCHED_RR）的情况下，每个进程被分配一个固定的时间片，当时间片用完后，进程就会被迫让出 CPU，等待下一次调度 。这就像是一场限时演讲比赛，每个选手的演讲时间一到，就必须下台，让下一位选手上台演讲 。通过这些调度时机的合理把握，Linux 系统能够高效地管理进程，确保每个进程都能在合适的时间运行，提高系统的整体性能 。

四、Linux进程终止

4.1 终止原因

进程终止是进程生命周期的最后阶段，就像是一场演出的落幕。进程终止的原因多种多样，常见的有以下几种 。

当进程调用exit函数时，它就像是一个演员主动向导演示意演出结束，决定主动终止自己的运行 。在 C 语言中，exit函数是标准库函数，用于正常终止程序的执行 。它接受一个整数参数，这个参数通常被称为退出状态码，用于向父进程或操作系统传递进程终止的相关信息 。比如，退出状态码为 0 通常表示进程正常结束，就像一场演出完美谢幕；而其他非零值则表示进程在执行过程中遇到了问题，比如文件读取失败、内存分配错误等，就像是演出过程中出现了意外状况 。

进程收到特定信号也会导致其终止 。信号是 Linux 系统中进程间通信的一种方式，它就像是一个紧急通知，当进程收到某些特定信号时，可能会被迫终止 。例如，SIGKILL信号是一个强制终止信号，它就像是一把 “尚方宝剑”，一旦发送给进程，进程就会立即无条件终止，没有任何机会进行资源清理或其他善后工作 。SIGTERM信号则相对温和一些，它是一个正常的终止信号，用于通知进程优雅地终止 。当进程收到SIGTERM信号时，它可以选择捕获这个信号，并在信号处理函数中进行一些清理工作，如关闭打开的文件、释放内存等，然后再正常终止 。就好比一个演员在收到导演的 “谢幕” 通知后，会先整理好自己的道具和服装，然后再优雅地退场 。

4.2终止过程

当进程调用exit函数后，会经历一系列复杂而有序的步骤，最终完成终止过程 。这个过程就像是一场精心安排的闭幕式，每个环节都至关重要 。

exit函数最终会调用内核中的do_exit函数，do_exit函数就像是这场闭幕式的总导演，负责协调和执行进程终止的各个环节 。do_exit函数首先会设置进程描述符task_struct的标志成员为PF_EXITING，这个标志就像是一个 “演出结束” 的牌子，向系统表明该进程正在退出 。

接着，do_exit函数会调用del_timer_sync函数删除任意内核定时器 。内核定时器就像是进程演出过程中的定时提醒装置，在进程终止时，这些定时器不再需要，所以要将它们删除 。

如果 BSD 的进程记账功能是开启的，do_exit函数会调用acct_update_integrals函数来输出记账信息 。进程记账功能就像是一个记录进程 “演出开销” 的账本，记录了进程占用 CPU 时间等信息，在进程终止时，需要将这些信息输出 。

然后，do_exit函数会调用exit_mm函数释放进程占用的mm_struct，如果没有别的进程使用（即没有被共享），就会彻底释放 。mm_struct结构体管理着进程的虚拟内存空间，就像是进程的 “演出场地”，在进程终止时，要将这个场地归还给系统 。

do_exit函数还会调用exit_sem函数，如果进程排队等待 IPC（进程间通信）信息，则让它离开该队列 。IPC 就像是进程之间的 “交流渠道”，在进程终止时，要断开这些交流渠道 。

调用exit_files和exit_fs函数，分别处理文件描述符和文件系统数据的引用计数 。如果引用计数降为 0，说明没有其他进程使用这些资源，这时就可以释放它们 。文件描述符和文件系统数据就像是进程演出时使用的 “道具”，在演出结束后，要将这些道具妥善处理 。

do_exit函数会把task_struct中的exit_code成员（退出代码）置为exit函数传入的参数或其他相关值，这个退出代码会供父进程检索，用于了解子进程终止的原因 。就好比演员在退场时，会给导演留下一张便条，说明自己退场的原因 。

do_exit函数会调用exit_notify函数向父进程发送信号，告知父进程自己即将终止 。同时，会给该进程寻找一个 “养父”，这个 “养父” 可能是线程组的其他线程或init进程 。并且会把进程状态改为EXIT_ZOMBIE（僵尸状态） 。在僵尸状态下，进程虽然已经基本停止运行，但它的进程描述符等信息还会被保留，直到父进程对其进行处理 。

do_exit函数会调用schedule函数切换到新的进程 。此时，原进程已经完成了大部分的终止工作，系统会调度其他可运行的进程继续执行，就像是一场演出结束后，舞台会为下一场演出做好准备 。

4.3僵死进程与避免

僵死进程，也被称为僵尸进程，是 Linux 系统中一种特殊的进程状态 。当子进程先于父进程退出，且父进程没有及时读取子进程的退出状态时，子进程就会进入僵死状态，成为僵死进程 。这就好比一个孩子提前离开了舞台，但家长却没有来接他，他只能在舞台边等待 。

僵死进程会在系统中保留其进程描述符、进程 ID 等信息，虽然它不再占用大量的系统资源，但如果大量的僵死进程存在，会占用有限的进程 ID 资源，导致系统无法创建新的进程 。这就像是舞台边挤满了等待家长的孩子，使得新的演员无法上台表演 。

为了避免僵死进程的产生，可以采取以下几种方法 。父进程可以调用wait系列函数（如wait、waitpid）来等待子进程结束，并获取子进程的退出状态 。wait函数会使父进程阻塞，直到有子进程退出，然后它会收集子进程的信息，并把它彻底销毁 。waitpid函数则更加灵活，它可以指定等待特定的子进程，并且可以设置非阻塞模式 。这就好比家长在孩子表演结束后，及时到舞台边接孩子，将孩子安全地带回家 。

父进程可以安装SIGCHLD信号的处理函数 。当子进程退出时，系统会向父进程发送SIGCHLD信号，父进程可以在信号处理函数中调用waitpid函数来处理子进程的退出，这样可以避免父进程阻塞，提高程序的并发性能 。这就好比家长给孩子设置了一个信号器，当孩子表演结束时，信号器会通知家长，家长可以及时去接孩子 。

还可以使用 “两次fork” 的技巧 。父进程先fork出一个子进程，然后子进程再fork出一个孙子进程，接着子进程立即exit退出 。这样，孙子进程就会成为孤儿进程，被init进程收养，init进程会负责清理孙子进程，从而避免了僵死进程的产生 。这就好比家长让孩子先找到一个临时监护人，然后自己离开，临时监护人会照顾好孩子，确保孩子不会无人照料 。通过这些方法，可以有效地避免僵死进程的产生，保证系统的稳定运行 。

五、Linux进程案例分析

Linux的调度器类主要实现两类进程调度算法：实时调度算法和完全公平调度算法(CFS)，实时调度算法SCHED_FIFO和SCHED_RR，按优先级执行，一般不会被抢占。直到实时进程执行完，才会执行普通进程。而大多数的普通进程，用的就是CFS算法。

进程调度的时机：

①进程状态转换时刻：进程终止、进程睡眠；

②当前进程的”时间片”用完；

③主动让出处理器，用户调用sleep()或者内核调用schedule()；

④从中断，系统调用或异常返回时。

每个进程task_struct中都有一个struct sched_entity se成员，这就是调度器的实体结构，进程调度算法实际上就是管理所有进程的这个se。

CFS基于一个简单的理念：所有任务都应该公平的分配处理器。理想情况下，n个进程的调度系统中，每个进程获得1/n处理器时间，所有进程的vruntime也是相同的。

CFS完全抛弃了时间片的概念，而是分配一个处理器使用比来度量。每个进程一个调度周期内分配的时间(类似于传统的“时间片”)跟三个因素有关：进程总数，优先级，调度周期

5.1理解CFS的首先要理解vruntime的含义

简单说vruntime就是该进程的运行时间，但这个时间是通过优先级和系统负载等加权过的时间，而非物理时钟时间，按字面理解为虚拟运行时间，也很恰当。

每个进程的调度实体se都保存着本进程的虚拟运行时间。

而进程相关的调度方法如下：

5.2vruntime的值如何跟新？

时钟中断产生时，会依次调用tick_periodic()-> update_process_times()->scheduler_tick()。

这里分析两个重要函数update_curr()和check_preempt_tick()。

主要关心__update_curr()函数。

关注calc_delta_fair()加权函数如何实现。

若当前进程nice为0，直接返回实际运行时间，其他所有nice值的加权都是以0nice值为参考增加或减少的。

当nice!=0时，实际是按公式delta *= weight / lw来计算的weight=1024是nice0的权重，lw是当前进程的权重，该lw和nice值的换算后面介绍，上面还书的lw计算公式没弄明白，总之这个函数就是把实际运行时间加权为进程调度里的虚拟运行时间，从而更新vruntime。

更新完vruntime之后，会检查是否需要进程调度。

更新完cfs_rq之后，会检查当前进程是否已经用完自己的“时间片”。

当该进程运行时间超过实际分配的“时间片”，就标记调度标志resched_task(rq_of(cfs_rq)->curr);，否则本进程继续执行。中断退出，调度函数schedule()会检查此标记，以选取新的进程来抢占当前进程。

5.3如何选择下一个可执行进程

CFS选择具有最小vruntime值的进程作为下一个可执行进程，CFS用红黑树来组织调度实体，而键值就是vruntime。那么CFS只要查找选择最左叶子节点作为下一个可执行进程即可。实际上CFS缓存了最左叶子，可以直接选取left_most叶子。

上面代码跟踪到timer tick中断退出，若“ideal_runtime”已经用完，就会调用schedule()函数选中新进程并且完成切换。

如果进程状态已经不是可运行，那么会将该进程移出可运行队列，如果继续可运行put_prev_task()会依次调用put_prev_task_fair()->put_prev_entity()。

__enqueue_entity(cfs_rq, prev) 将上一个进程重新插入红黑树(注意，当前运行进程是不在红黑树中的)pick_next_task()会依次调用pick_next_task_fair()。

set_next_entity()函数会调用__dequeue_entity(cfs_rq, se)把选中的下一个进程即最左叶子移出红黑树。最后context_switch()完成进程的切换。

5.4何时更新rbtree

①上一个进程执行完ideal_time，还可继续执行时，会插入红黑树；

②下一个进程被选中移出rbtree红黑树时；

③新建进程；

④进程由睡眠态被激活，变为可运行态时；

⑤调整优先级时也会更新rbtree。

5.5新建进程如何加入红黑树

新建进程会做一系列复杂的工作，这里我们只关心与红黑树有关部分

Linux使用fork，clone或者vfork等系统调用创建进程，最终都会到do_fork函数实现，如果没有设置CLONE_STOPPED，do_fork会执行两个与红黑树相关的函数: copy_process()和wake_up_new_task()

计算新进程的vruntime值，加上一个“平均时间片”表示刚执行完，避免新建进程立马抢占CPU。

更新时钟，激活新建的进程activate_task()会调用。

将新建的进程加入rbtree。

5.6唤醒进程

调用try_to_wake_up()->activate_task()->enqueue_task_fair()->enqueue_entity()注意enqueue_entity 函数调用place_entity对进程vruntime做补偿计算，再次考察place_entity(cfs_rq, se, 0)。

当initial=1时，新建进程vruntime=cfs最小vruntime值+时间片，放入红黑树最右端。

当initial=0时，表示唤醒进程，vruntime要减去一个thresh.这个thresh由调度周期sysctl_sched_latency加权得到虚拟时间，这样做可以对睡眠进程做一个补偿，唤醒时会得到一个较小的vruntime, 使它可以尽快抢占CPU(可以快速响应I/O消耗型进程)。

注意注释/* ensure we never gain time by being placed backwards. */这个设计是为了给睡眠较长时间的进程做时间补偿的，既使其可以快速抢占，又避免因太小的vruntime值而长期占用CPU。但有些进程只是短时间睡眠，这样唤醒时自身vruntime还是大于min_vruntime的，为了不让进程通过睡眠获得额外运行时间补偿，最后vruntime取计算出的补偿时间和进程本身的vruntime较大者。从这可以看出，虽然CFS不再区分I/O消耗型，CPU消耗型进程，但是CFS模型对IO消耗型天然的提供了快速的响应。

5.7改变进程优先级，如何调整rbtree

Linux中改变进程优先级会调用底层的set_user_nice()。

set_user_nice把进程从红黑树取出，调整优先级(nice值对应权重)，再重新加入红黑树。

set_load_weight()函数是设置nice值对应的权重。

数组prio_to_weight[]是将nice值(-20~19)转化为以nici 0(1024)值为基准的加权值,根据内核注释每一个nice差值，权重相差10%，即在负载一定的条件下，每增加或减少一个nice值，获得的CPU时间相应增加或减少10%。

上面calc_delta_mine()函数用到这个数组加权值，这个转化过程还没弄明白，有明白的朋友，指点一二，不胜感激。

最后，说下对CFS “完全公平” 的理解：

①不再区分进程类型，所有进程公平对待

②对I/O消耗型进程，仍然会提供快速响应(对睡眠进程做时间补偿)

③优先级高的进程，获得CPU时间更多(vruntime增长的更慢)

可见CFS的完全公平，并不是说所有进程绝对的平等，占用CPU时间完全相同，而是体现在vruntime数值上，所有进程都用虚拟时间来度量，总是让vruntime最小的进程抢占，这样看起来是完全公平的，但实际上vruntime的更新，增长速度，不同进程是不尽一样的。CFS利用这么个简单的vruntime机制，实现了以往需要相当复杂算法实现的进度调度需求，高明！