您现在的位置是：首页 > Linux OSLinux OS
深入理解Linux进程调度(上)---程磊篇
转载2022-08-07【Linux OS】人已围观
简介作者简介：程磊，一线码农，在某手机公司担任系统开发工程师，日常喜欢研究内核基本原理。
作者简介：
程磊，一线码农，在某手机公司担任系统开发工程师，日常喜欢研究内核基本原理。
目录
一、进程调度概览
二、进程调度框架
三、SMP管理
四、基本分时调度
五、总结回顾
一、进程调度概览
进程调度是操作系统最重要的内容之一，也是学习操作系统的重点和难点。关于进程调度，我们首先就会问出一些问题，什么是进程调度，为什么要进程调度，如何进行调度。下面我们用一幅图把这些问题关联起来：
这张图把进程调度的所有问题和知识点都关联了起来，本文后面所有的内容都是对这张图的解释和扩展延伸，下面让我们来一一讲解。
1.1 什么是调度
什么是调度？调度是CPU资源管理器。操作系统的作用之一就是系统资源管理器。CPU是计算机系统中最重要的资源，当然也要管理。所有进程的运行都需要CPU，对CPU该如何管理呢？对于直接共享型的事物，我们有两种管理方法：一种是时间分割管理，另一种是空间分割管理。由于CPU自身的特性，没有空间分割相似性，只有时间分割相似性，所以我们只能对CPU进行时间分割管理。对CPU进行时间分割管理的具体做法就叫做进程调度。
那么调度的是什么呢？进程调度，调度的当然是进程啦，也对也不对。我们知道进程是资源分配的单位，线程是执行的单位。早期的时候没有多线程，进程就是线程，线程就是进程，所以此时进程调度调度的是进程。但是当有了多线程之后，线程变成了执行的单位，进程不再是执行的单位，进程调度调度的就是线程了。不过由于历史原因，大家都习惯叫进程调度，所以现在这个领域的名称还是叫进程调度。后文中说到调度进程的地方都是调度的线程，由于习惯问题，我们还说调度进程不说调度线程，请大家要注意。
对线程的调度可以有两种方式：一种是直接调度线程，不考虑它们所属的进程，这种方式叫做直接调度或者一级调度；另一种是先调度进程，再在进程内部调度线程，这种方式叫做间接调度或者二级调度。POSIX规定，操作系统可以选择这两种方式中的任何一种都行。Linux选择的是一级调度，为什么会这么选择呢？主要是为了提高进程的并发性，充分利用多CPU多核的优势。如果使用二级调度的话，看似每个进程之间都公平了，但是有些进程的计算量比较大，就无法通过多开线程提高自己的性能，这样对系统整体的性能是有害的，也不利用发挥计算机多CPU的优势。一级调度看似对有些进程不公平，但是计算量小的进程少开线程，计算量大的进程多开线程，相对还是很公平的。
就像国家希望每个企业都做大做强，但是同时也会反垄断一样。Linux也推出了cgroup组调度机制，来限制某个或者某一类进程对CPU资源的过度占用。本文中不讲cgroup组调度机制，后文的讲解都是假设没有cgroup组调度。
1.2 为什么要调度
我们知道了什么是调度，那么为什么要调度呢，没有调度会怎么样呢？最早的计算机是没有调度的，程序只能一个一个地运行，一个进程死亡之后才能去运行下一个进程。这里面首先存在的问题就是我们没法同时运行多个进程。其次就算我们不需要同时运行多个进程，程序在运行的过程中如果要等IO，CPU就只能空转，这也十分浪费CPU资源。于是最早的多任务——协作式多任务诞生了，当程序由于要等IO而阻塞时就会去调度执行其它的进程。但是协作式多任务存在着很大的问题，就是每个进程运行的时间片长短是不确定的，而且是很偶然很随机的。如果一个进程它一直在做运算就是不进行IO操作，那么它就会一直霸占CPU。针对这个问题，当时想出的方法是道德解决方案。内核向进程提供系统调用sched_yield，它会使进程主动放弃CPU让其它进程来执行。然后要求所有的程序员在程序中合适的地方尽量多地加入sched_yield调用。这个方法在当时是管用的，因为当时计算机的使用者(同时也是程序员)仅限于少数科研机构和政府机关的部分人员，一台电脑的共同使用者都认识，面子上还得过得去。
后来随着计算机的普及，以及计算机的使用者和程序员这两个角色的分离，主要靠道德约束的协作式多任务已经行不通了，我们需要强制性多任务，也就是抢占式多任务。抢占式多任务使得每个进程都可以相对公平地平分CPU时间，如果一个进程运行了过长的时间就会被强制性地调度出去，不管这个进程是否愿意。有了抢占式多任务，我们在宏观上不仅可以同时运行多个进程，而且它们会一起齐头并进地往前运行，不会出现某个进程被饿死的情况，这样我们使用电脑的体验就非常完美了。抢占式多任务和协作式多任务不是对立的，它们是相互独立的，可以同时存在于系统中。
抢占又分为用户抢占和内核抢占。由于抢占对进程来说是异步的，进程被抢占时不一定运行在什么地方，有可能运行在用户空间，也有可能运行在内核空间(进程通过系统调用进入内核空间)。如果抢占点是在用户空间，那么抢占就是安全的，如果在内核空间就不一定安全，这是为什么呢？因为对于用户空间来说，如果抢占会导致线程同步问题，那么用户空间有责任使用线程同步机制来保护临界区，只要用户空间做好同步就不会出问题。如果内核也做好了同步措施，内核抢占也不会出问题，但是内核最初的设计就没有考虑内核抢占问题，所以刚开始的时候内核是不能抢占的。后来内核开发者对内核进行了完善，把内核所有的临界区都加上了同步措施，然后内核就是可抢占的了。内核能抢占了不代表内核一定会抢占，内核会不会抢占由config选项控制，可以开启也可以关闭，因为内核抢占还会影响系统的响应性和性能。开启内核抢占会提高系统的响应性但是会降低一点性能，关闭内核抢占会降低系统的响应性但是会提高一点性能。因此把内核抢占做成配置项，可以让大家灵活配置。服务器系统一般不需要与用户交互，所以会关闭内核抢占来提高性能，桌面系统会开启内核抢占来提高系统的响应性，来增加用户体验。
现在我们再来看一下为什么要调度。因为如果没有调度的话，就不能实现多任务，一次就只能运行一个程序，我们使用电脑的体验就会大大降低。有了调度就有了多任务，我们就能同时在电脑上做很多事情，使用体验就会非常好。
1.3 为什么能调度
我们再来看看为什么能调度呢。我们把协作式多任务叫做主动调度，抢占式多任务叫做被动调度。为什么能调度分为两部分：为什么能触发调度和为什么能执行调度。对于主动调度，调度是进程主动触发的，这个是肯定能的。对于被动调度，在图灵机模型中是做不到的，因为图灵机是一条线性一直往前走的，进程在执行时，进程要是不主动，是不可能跳到其它进程来执行的。被动调度能做到的原因关键就在于中断机制，因为中断是强行在正常的执行流中插入了一段代码，它能改变后续代码的走向。有了中断机制，我们就可以创建一个定时器中断，以固定的时间间隔比如每10ms来触发中断，检测进程是否运行时间过长，如果过长就触发调度。这样任何进程都不可能霸占CPU，所以进程都能公平地共享CPU时间。这里引用其中的一幅图来看一下：
可以看到在纯图灵机模型中，进程如果不主动进行调度，是没有外力强迫进程进行调度的，进程就能一直霸占CPU。有了中断机制之后，在中断的处理中可以触发调度，在中断返回的点可以执行调度，这样就可以避免进程霸占CPU了。
前面说的是为何能触发进程调度，主动调度是进程自己触发的，被动调度是在中断中触发的。现在来看看为何能执行调度，执行调度包括两部分：选择进程和切换进程。选择进程是纯软件的，肯定能实现。切换进程是怎么切换呢？一个进程执行的好好的，怎么就切换了呢，需不需要硬件的支持呢？进程切换主要是切换执行栈和用户空间，这两个都需要用到CPU特定的指令。进程切换的具体原理和细节我们在2.7节中讲。
1.4 何时调度
我们前面已经讲了主动调度(协作式多任务)和被动调度(抢占式多任务)。
对于主动调度，触发调度和执行调度是同步的、一体的，触发即执行。主动调度发生的时机有IO等待、加锁失败等各种阻塞操作以及用户空间主动调用sched_yield。
对于被动调度，触发调度和执行调度是异步的、分离的，触发调度并不会立马执行调度，而是做个需要调度的标记，然后在之后的某个合适的地方会检测这个标记，如果被设置就进行调度。触发调度的点有：在定时器中断中发现当前进程超时了，在唤醒进程时发现新进程需要抢占当前进程，在迁移进程时发现新进程需要抢占当前进程，在改变进程优先级时发现新进程需要抢占当前进程。其中第一个触发点是当前进程需要被抢占，它是用来保证公平调度，防止进程霸占CPU的，后三个触发点是新进程需要抢占当前进程，它是用来提高系统响应性的。执行调度的点有：系统调用完成之后即将返回用户空间，中断完成之后即将返回用户空间，如果开启了内核抢占的话则还有,中断完成之后即将返回内核,如果中断发生在禁止抢占临界区中，那么中断完成之后返回内核是不会执行调度的，而是会在临界区结束的时候执行调度。下面我们借用《深入理解Linux中断机制》中的几个图来看一下这几个执行调度检测点：
系统调用完成之后即将返回用户空间和中断完成之后即将返回用户空间，是非常好的执行进行调度的点，也就是此图中的三个箭头的地方。CPU异常在意义上不是系统调用，但是在形式上和逻辑上相当于是系统调用。
中断发生在内核空间的场景，如果开启了内核抢占，如果被抢占的内核代码不是在禁用抢占临界区，中断返回时是执行调度的点。如果被抢占的内核代码在禁用抢占临界区中，在执行调度的点被推迟到了临界区的出口处。
1.5 如何调度
现在到了执行调度的时刻了。执行调度分为两步：一是选择下一个要执行的进程，二是切换进程。选择下一个要执行的进程，这就是调度算法了。首先调度算法只能从Runnable的进程中进行选择，不能选择Blocked进程，因为选择了也没有意义。其次算法还要区分进程类型，比如普通进程与实时进程，肯定要优先选择实时进程，在同一类型的进程中还要有具体的算法来决定到底选择哪个进程。在Linux中一共把进程分为了5类，每一类都有一个具体的算法。类之间的关系是优先选择高类的进程，只有当高类没有Runnable进程时才会去选择低类进程。
进程选择好了之后就要切换进程了。切换进程分两步：第一步是切换用户空间，第二步是切换执行栈(线程栈)。如果要切换的两个线程属于同一个进程就不需要切换用户空间了。切换用户空间是一个CPU架构相关的事情，在x86 CPU上是给CR3寄存器赋值新进程的页表树的根指针。此时切换的执行栈是线程的内核栈，执行栈代表的是当前线程的执行情况，切换执行栈就是切换线程。线程的用户栈信息都在内核栈里保存着。切换完内核栈之后，线程继续执行就会返回用户空间，由于此时用户空间已经切换完成，内核栈上也保存着用户栈的信息，所以线程能返回到正确的用户空间线程上去。
下面我们画个图来看一下：
对于一个CPU来说，永远只有一个当前进程在运行，当执行进程调度时，需要从其它进程中选择一个进程，把它旋转到最下方作为当前进程，它就开始运行了。
1.6 调度均衡
前面所说的都是针对一个CPU的情况，对于多个CPU来说，每个CPU也是这样的逻辑。但是有一点不同的是，如果一个系统上的多个CPU忙的忙死闲的闲死，显然不太好，因此多个CPU之间会进行调度均衡。调度均衡可以分为个体均衡和总体均衡。个体均衡是从进程的角度出发选择到一个相对清闲的CPU上去运行。总体均衡是从CPU的角度出发如何从别的CPU上拉取一些进程到自己这来执行，使得所有CPU的工作量尽量平均。个体均衡的触发点有三个：一是新进程刚创建时，二是进程要执行新程序时，三是进程被唤醒时，在这三个点进程都可以选择去哪个CPU的运行队列上去等待执行。在个体均衡下，每个进程都尽量选择相对清闲的CPU，所以所有CPU的负载应该还是会比较均衡的。但是时间长了可能还是会出现负载不均衡的情况，此时就要进行总体均衡了。总体均衡的触发点有三个：一是CPU即将idle前会去找到最忙的CPU然后拉取一些任务过来；二是定时器中断的周期性检测，会检查是否所有的CPU都一样忙，如果忙闲差别太大就会进行进程迁移，使得所有CPU忙闲程度接近；三是在idle进程中如果CPU发现自己太忙而有的CPU在idle就会唤醒那个CPU进行负载均衡。
1.7 调度器评价
狭义的调度器指的是具体的调度算法，广义的调度器指的是整个调度体系。不过两者的评价指标是相同的，所以我们这里不具体区分调度器是指调度算法还是调度体系。调度器的评价指标有以下几个：
1.响应性，当一个进程发生事件需要去处理的时候能否及时被调度。这一点和使用体验是密切相关的，当我们用鼠标点击一个程序的时候，肯定希望程序立即能做出响应，如果程序过了好几秒才有反应，那我们肯定会很烦的。
2.吞吐量，系统在相同的时间内能够运行更多的程序、执行更多的指令。这个首先要求调度器本身的代码要尽量的高效。如果调度器写得非常复杂，运行一次就需要好几毫秒的话，那留给进程运行的时间就不多了。其次进程调度的频率要低，如果进程调度的频率比较高的话，那调度器执行的次数就比较多，从而占用了较多的CPU时间，而且频繁切换进程也会影响缓存的性能。从这一点来看响应性和吞吐量是有矛盾的，提高响应性会增加进程切换的频率，而这会降低系统的吞吐量。
3.公平性，指的是相对公平性，每个进程实际获得的时间份额与应当获得的时间份额都相差不大。不会出现有些进程饥饿的情况，也不会出现有些进程获得过多时间份额的情况。
4.适应性，指的是系统无论是调度几个进程还是调度几万个进程，都能撑得住，都能收放自如，各项指标都不能受到太大的影响。
5.节能性，自从智能手机越来越普及，而手机的电池技术一直没有较大的突破，所以省电对手机来说就是一项非常重要的任务，调度器也不可避免地要考虑省电问题了。
1.8 调度器历史
Linux的调度器经历了长久的发展，是内核中被优化最多目前最完善的模块之一。下面我们来看一下Linux调度器发展的历史。
Traditional Scheduler: v1.0 – v2.4
这一阶段的调度器和传统的UNIX上的调度器逻辑是一样的。全局只有一个运行队列，所有进程都放在一个队列上。进程区分IO密集型和CPU密集型，根据进程的睡眠时间计算动态优先级，按照动态优先级决定进程的调度顺序，按照优先级分配进程的时间片大小，时间片大小是等差数列。进程在运行队列上并没有特定的排序，每次选择下一个进程的时候都要遍历整个队列，所以算法的时间复杂度是O(n)。在SMP上也只有一个运行队列，当CPU比较多进程也比较多的时候，锁冲突比较严重。
O(1) Scheduler: v2.5 – v2.6.22
此调度器主要是针对传统调度器进行了改进。首先把运行队列从单一变量变成了per-CPU变量，每个CPU一个运行队列，这样就不会有锁冲突了，不过这样就需要调度均衡了。其次把运行队列的一个链表分成了两个链表数组：活动数组和过期数组。时间片没用耗尽的进程放在活动数组中，时间片耗尽的进程放在过期数组中，当所有进程的时间片都耗尽的时候交换两个数组，重新分配时间片。两个数组都使用动态优先级排序，并用bitmap来表示哪个优先级队列中有可运行的进程，把选择进程的算法复杂度降低到了O(1)。对进程区分IO密集型和CPU密集型并计算动态优先级这一点和传统调度器一样没有变。
SD Scheduler：(未合入)
楼梯调度器，它是对O(1)调度器的改进，算法复杂还是O(1)。之前的调度器都区分IO密集型和CPU密集型，算法要对进程的类型进行探测，根据探测结果调整动态优先级。这就有很大的问题，探测不一定准确，而且进程还可以欺骗调度器，最终会导致调度有很大的不公平性。楼梯调度器是第一次尝试使用公平调度算法，它废除了动态优先级，不再区分IO密集型进程和CPU密集型进程，但是仍然让IO密集型进程保持较高的响应性。在实现上，楼梯调度算法废弃了过期数组，只使用一个数组。当进程使用完自己的时间片之后，其时间片就会被减半并下降到下一个优先级，其本身的优先级还是不变的。当进程下降到最后一个优先级之后就再回到它本来的优先级队列并重新分配时间片。整个过程就像下楼梯一样，所以这个算法就叫做楼梯调度器。此算法虽然没有合入到标准内核，但是它第一次证明了可以采取完全公平的思想进行调度，也就是不区分IO密集型和CPU密集型进程。
RSDL Scheduler：(未合入)
旋转楼梯调度器，是对楼梯调度器的改进。又重新引入了过期数组，为每个优先级都分配一个组时间配额记为Tg，进程本身的时间片记为Tp。当进程用完自己的时间片时会下降一个优先级，当一个优先级的Tg被用完时，组内所有的进程都会下降一个优先级。进程下降到最低优先级之后会被放入过期数组，当活动数组为空时就会交换活动数组和过期数组。由于加了Tg，使得低优先级进程的调度延迟可控，进一步增加了公平性。
CFS: Completely Fair Scheduler: v2.6.23 – now
完全公平调度器，从SD/RSDL中吸取了完全公平的思想，不再区分IO密集型进程与CPU密集型进程，不再根据睡眠时间调整动态优先级，所有普通进程都按优先级相对平分CPU时间，算法复杂度是O(logn)。此时对调度器框架也进行了重构，和之前的有很大的不同。之前的调度器是一个算法调度所有进程，在算法内部区别对待实时进程和普通进程。现在的调度器框架是先区分不同类型的进程，普通进程一个调度类，实时进程一个调度类，调度类里面再去实现具体的调度算法。CFS是普通调度类的算法。
二、进程调度框架
前面我们对进程调度的概念和逻辑进行了讲解，现在我们来看一下Linux上进程调度的框架结构。本章只讲总体框架，不讲具体算法，具体算法在后面的章节中讲。
2.1 调度队列
我们先来看一下进程的状态转换图。
处于就绪(Runnable)状态的进程可以被调度到CPU上去执行。但是处于就绪状态的进程可能不止一个，所以我们需要一个运行队列来安放所有就绪的进程，由于CPU也不止一个，所以我们需要NR_CPU个运行队列。
我们看一下调度队列的定义(代码经过了高度删减)：
linux-src/kernel/sched/sched.h
struct rq {
raw_spinlock_t __lock;
unsigned int nr_running;
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
struct task_struct __rcu *curr;
struct task_struct *idle;
struct task_struct *stop;
int cpu;
int online;
};linux-src/kernel/sched/core.c
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
内核定义了一个per-CPU变量runqueues，其类型是struct rq。所有的就绪进程都会被放入某个CPU的rq上去，具体放到哪个rq上，这个在调度均衡里面讲。内核一共定义了五个调度类(这个在2.5中细讲)，属于不同调度类的进程会被放入不同的子队列，所以rq中包含三个子运行队列cfs_rq、rt_rq、dl_rq。为啥只有3个子运行队列呢？因为有两个调度类idle、stop，每个CPU只能有一个进程，所以没必要弄个队列，直接关联它们的进程就可以了，就是上面代码中的两个struct task_struct * 类型的指针变量idle、stop。
2.2 进程唤醒
进程是怎么被放入运行队列的呢？都是通过进程唤醒来放入的，包括新创建的进程也是。新建唤醒和阻塞唤醒的代码不太一样，下面我们分别来看一下。
我们先来看一下新建唤醒的代码：
linux-src/kernel/sched/core.c
void wake_up_new_task(struct task_struct *p)
{
struct rq_flags rf;
struct rq *rq;
raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
WRITE_ONCE(p->__state, TASK_RUNNING);
p->recent_used_cpu = task_cpu(p);
rseq_migrate(p);
__set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));
rq = __task_rq_lock(p, &rf);
update_rq_clock(rq);
activate_task(rq, p, ENQUEUE_NOCLOCK);
check_preempt_curr(rq, p, WF_FORK);
task_rq_unlock(rq, p, &rf);
}在fork中会调用此函数唤醒新创建的进程，把它放入到运行队列中等待被调度。此函数会先调用select_task_rq来选择自己要去哪个CPU的rq上去，然后调用activate_task把进程加入到相应的运行队列上，最后调用check_preempt_curr看一下是否需要抢占，如果需要就触发抢占。select_task_rq的逻辑我们在调度均衡中讲，check_preempt_curr的逻辑我们在下一节的被动调度中讲。
我们再来看一下阻塞唤醒的代码：
linux-src/kernel/sched/core.c
static int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
unsigned long flags;
int cpu, success = 0;
preempt_disable();
if (p == current) {
goto out;
}
raw_spin_lock_irqsave(&p->pi_lock, flags);
if (!ttwu_state_match(p, state, &success))
goto unlock;
if (READ_ONCE(p->on_rq) && ttwu_runnable(p, wake_flags))
goto unlock;
cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);
if (task_cpu(p) != cpu) {
if (p->in_iowait) {
delayacct_blkio_end(p);
atomic_dec(&task_rq(p)->nr_iowait);
}
wake_flags |= WF_MIGRATED;
set_task_cpu(p, cpu);
}
ttwu_queue(p, cpu, wake_flags);
unlock:
raw_spin_unlock_irqrestore(&p->pi_lock, flags);
out:
preempt_enable();
return success;
}
int wake_up_process(struct task_struct *p)
{
return try_to_wake_up(p, TASK_NORMAL, 0);
}
int wake_up_state(struct task_struct *p, unsigned int state)
{
return try_to_wake_up(p, state, 0);
}
int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flags,
void *key)
{
WARN_ON_ONCE(IS_ENABLED(CONFIG_SCHED_DEBUG) && wake_flags & ~WF_SYNC);
return try_to_wake_up(curr->private, mode, wake_flags);
}阻塞唤醒的核心逻辑是try_to_wake_up，但是内核并不是直接用这个函数，而是提供了三个封装函数。wake_up_process是默认的通用的进程唤醒接口，能唤醒TASK_NORMAL状态的进程。TASK_NORMAL就是阻塞状态的进程，包含TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE，前者是前睡眠能被信号唤醒，后者是深睡眠不能被信号唤醒。还有一些特殊状态的进程如被暂停的进程是不能通过wake_up_process来唤醒的，所以内核还提供了接口wake_up_state，可以自己指定唤醒什么状态的进程。还有一个封装函数default_wake_function，它是wait_queue的默认唤醒函数。
try_to_wake_up函数首先进行一些检测，先检测被唤醒的进程是否为当前进程，如果是的话直接go out。再检测进程的状态是否与state相符合，不符合就不唤醒，再看一下进程是否已经处于唤醒状态了，如果是就没有必要唤醒了。然后调用select_task_rq选择要到哪个CPU的运行队列上去运行，最后调用ttwu_queue把进程放到目标运行队列上去。基本逻辑和wake_up_new_task是一样的。
2.3 调度时机
进程放入运行队列之后就等着被调度到CPU上去运行了。但是当前进程正在使用着CPU，它什么时候能把CPU让给其它进程去运行呢？有两种情况：一是当前进程主动让出CPU，这叫主动调度；二是当前进程被动让出CPU，这叫被动调度，也就是进程抢占。
主动调度：
主动调度又可以分为自愿性主动调度和非自愿性主动调度。自愿性主动调度是指进程主动调用sched_yield让出CPU，进程本身还会回到运行队列中去等待下次调度。如果运行队列中没有其它进程的话，此进程还会继续运行。非自愿性主动调度是指进程运行时遇到了无法继续运行的情况，只能进行调度让其它进程运行。进程无法继续运行的情况有加锁失败、要读的文件现在不在内存中、进程死亡等。
下面我们来看一个非自愿性主动调度的例子，信号量获取失败时的操作：
linux-src/kernel/locking/semaphore.c
static inline int __sched __down_common(struct semaphore *sem, long state, long timeout)
{
struct semaphore_waiter waiter;
list_add_tail(&waiter.list, &sem->wait_list);
waiter.task = current;
waiter.up = false;
for (;;) {
if (signal_pending_state(state, current))
goto interrupted;
if (unlikely(timeout <= 0))
goto timed_out;
__set_current_state(state);
raw_spin_unlock_irq(&sem->lock);
timeout = schedule_timeout(timeout);
raw_spin_lock_irq(&sem->lock);
if (waiter.up)
return 0;
}
timed_out:
list_del(&waiter.list);
return -ETIME;
interrupted:
list_del(&waiter.list);
return -EINTR;
}先定义一个等待项，把自己加入到信号量的等待列表中，然后调用schedule_timeout执行调度。schedule_timeout和普通的调度函数schedule的区别是：schedule只能等着被具体的事件唤醒，schedule_timeout可以被事件唤醒，如果事件在规定的时间没有到来就会被定时器超时唤醒。
被动调度：
如果进程自己不调用sched_yield，也不调用任何会阻塞的函数，那么进程岂不是就可以一直霸占着CPU了。所以内核还提供了被动调度，强制进行进程调度，避免一个进程长时间霸占CPU。被动调度是被动的，不能由进程主动去调度，所以被动调度和主动调度的模式差别很大。被动调度的过程分为两步：触发调度和执行调度。触发调度仅仅是做个标记，告诉系统需要调度了。执行调度是系统会在某些特定的点去检查调度标记，如果被设置的话就执行调度。触发调度的点有：定时器中断、唤醒进程时、迁移进程时、改变进程优先级时。执行调度的点有：从系统调用返回用户空间、从中断返回用户空间、从中断返回内核、禁用抢占临界区结束、禁用软中断临界区结束、cond_resched调用点。
定时器中断是保证抢占式多任务能实现的关键。因为其它被动调度的触发点是不确定的，只有定时器中断是确定的周期性的，因此定时器中断也被叫做调度tick。定时器中断的频率是个kconfig选项，可选的值有100、250、300、1000。默认选项是250，也就是说每4ms就会有一个定时器中断，这样就能保证被动调度的及时性，不会有进程过长的占用CPU。
下面我们来看一下调度tick的流程：
linux-src/kernel/sched/core.c
void scheduler_tick(void)
{
int cpu = smp_processor_id();
struct rq *rq = cpu_rq(cpu);
struct task_struct *curr = rq->curr;
curr->sched_class->task_tick(rq, curr, 0);
#ifdef CONFIG_SMP
rq->idle_balance = idle_cpu(cpu);
trigger_load_balance(rq);
#endif
}在低精度定时器、高精度定时器与固定tick、动态tick的不同组合下，定时器中断触发的方式是不同的，但是最终都会调用scheduler_tick。scheduler_tick会调用当前进程的调度类的task_tick函数，此函数根据具体的情况可能会触发调度。task_tick函数的实现细节我们在具体的调度算法中再讲。
唤醒进程有新建唤醒和阻塞唤醒，它们都有可能触发调度。我们来看一下：
linux-src/kernel/sched/core.c
void wake_up_new_task(struct task_struct *p)
{
struct rq_flags rf;
struct rq *rq;
__set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));
activate_task(rq, p, ENQUEUE_NOCLOCK);
check_preempt_curr(rq, p, WF_FORK);
}
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
unsigned long flags;
int cpu, success = 0;
cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);
if (task_cpu(p) != cpu) {
set_task_cpu(p, cpu);
}
ttwu_queue(p, cpu, wake_flags);
return success;
}
static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)
{
struct rq *rq = cpu_rq(cpu);
struct rq_flags rf;
ttwu_do_activate(rq, p, wake_flags, &rf);
}
static void
ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
struct rq_flags *rf)
{
int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
activate_task(rq, p, en_flags);
ttwu_do_wakeup(rq, p, wake_flags, rf);
}
static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
struct rq_flags *rf)
{
check_preempt_curr(rq, p, wake_flags);
WRITE_ONCE(p->__state, TASK_RUNNING);
}
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
if (p->sched_class == rq->curr->sched_class)
rq->curr->sched_class->check_preempt_curr(rq, p, flags);
else if (p->sched_class > rq->curr->sched_class)
resched_curr(rq);
}
void resched_curr(struct rq *rq)
{
struct task_struct *curr = rq->curr;
int cpu;
cpu = cpu_of(rq);
if (cpu == smp_processor_id()) {
set_tsk_need_resched(curr);
set_preempt_need_resched();
return;
}
}linux-src/include/linux/sched.h
static inline void set_tsk_need_resched(struct task_struct *tsk)
{
set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
}
static inline void set_tsk_thread_flag(struct task_struct *tsk, int flag)
{
set_ti_thread_flag(task_thread_info(tsk), flag);
}可以看到无论是新建唤醒还是阻塞唤醒，最终都是调用check_preempt_curr函数来处理的。如果被唤醒的进程和当前进程是同一个调度类的则会调用调度类的函数来处理，这个逻辑我们在具体调度类中再讲。如果被唤醒的进程比当前进程的调度类高，则会触发调度。resched_curr函数最终会在thread_info的flag中设置TIF_NEED_RESCHED标记。
下面我们再来看一下执行调度的点，以x86为例。
系统调用返回用户空间：
linux-src/arch/x86/entry/common.c
__visible noinstr void do_syscall_64(struct pt_regs *regs, int nr)
{
nr = syscall_enter_from_user_mode(regs, nr);
if (!do_syscall_x64(regs, nr) && !do_syscall_x32(regs, nr) && nr != -1) {
/* Invalid system call, but still a system call. */
regs->ax = __x64_sys_ni_syscall(regs);
}
syscall_exit_to_user_mode(regs);
}
static noinstr bool __do_fast_syscall_32(struct pt_regs *regs)
{
int nr = syscall_32_enter(regs);
int res;
syscall_enter_from_user_mode_prepare(regs);
do_syscall_32_irqs_on(regs, nr);
syscall_exit_to_user_mode(regs);
return true;
}
__visible noinstr void do_int80_syscall_32(struct pt_regs *regs)
{
int nr = syscall_32_enter(regs);
nr = syscall_enter_from_user_mode(regs, nr);
do_syscall_32_irqs_on(regs, nr);
syscall_exit_to_user_mode(regs);
}linux-src/kernel/entry/common.c
__visible noinstr void syscall_exit_to_user_mode(struct pt_regs *regs)
{
instrumentation_begin();
__syscall_exit_to_user_mode_work(regs);
instrumentation_end();
__exit_to_user_mode();
}
static __always_inline void __syscall_exit_to_user_mode_work(struct pt_regs *regs)
{
syscall_exit_to_user_mode_prepare(regs);
local_irq_disable_exit_to_user();
exit_to_user_mode_prepare(regs);
}
static void exit_to_user_mode_prepare(struct pt_regs *regs)
{
unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))
ti_work = exit_to_user_mode_loop(regs, ti_work);
}
static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,
unsigned long ti_work)
{
while (ti_work & EXIT_TO_USER_MODE_WORK) {
if (ti_work & _TIF_NEED_RESCHED)
schedule();
if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))
handle_signal_work(regs, ti_work);
ti_work = READ_ONCE(current_thread_info()->flags);
}
return ti_work;
}可以看到系统调用完成之后返回用户空间之前会检测thread_info flag中的_TIF_NEED_RESCHED，如果设置了就会执行调度。
中断返回用户空间或者内核空间：
linux-src/arch/x86/include/asm/idtentry.h
#define DEFINE_IDTENTRY_IRQ(func) \
static void __##func(struct pt_regs *regs, u32 vector); \
\
__visible noinstr void func(struct pt_regs *regs, \
unsigned long error_code) \
{ \
irqentry_state_t state = irqentry_enter(regs); \
u32 vector = (u32)(u8)error_code; \
\
instrumentation_begin(); \
kvm_set_cpu_l1tf_flush_l1d(); \
run_irq_on_irqstack_cond(__##func, regs, vector); \
instrumentation_end(); \
irqentry_exit(regs, state); \
}
#define DEFINE_IDTENTRY(func) \
static __always_inline void __##func(struct pt_regs *regs); \
\
__visible noinstr void func(struct pt_regs *regs) \
{ \
irqentry_state_t state = irqentry_enter(regs); \
\
instrumentation_begin(); \
__##func (regs); \
instrumentation_end(); \
irqentry_exit(regs, state); \
}linux-src/kernel/entry/common.c
noinstr void irqentry_exit(struct pt_regs *regs, irqentry_state_t state)
{
if (user_mode(regs)) {
irqentry_exit_to_user_mode(regs);
} else if (!regs_irqs_disabled(regs)) {
if (IS_ENABLED(CONFIG_PREEMPTION)) {
irqentry_exit_cond_resched();
}
} else {
if (state.exit_rcu)
rcu_irq_exit();
}
}
noinstr void irqentry_exit_to_user_mode(struct pt_regs *regs)
{
instrumentation_begin();
exit_to_user_mode_prepare(regs);
instrumentation_end();
__exit_to_user_mode();
}
static void exit_to_user_mode_prepare(struct pt_regs *regs)
{
unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))
ti_work = exit_to_user_mode_loop(regs, ti_work);
}
static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,
unsigned long ti_work)
{
while (ti_work & EXIT_TO_USER_MODE_WORK) {
if (ti_work & _TIF_NEED_RESCHED)
schedule();
if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))
handle_signal_work(regs, ti_work);
ti_work = READ_ONCE(current_thread_info()->flags);
}
return ti_work;
}
void irqentry_exit_cond_resched(void)
{
if (!preempt_count()) {
if (need_resched())
preempt_schedule_irq();
}
}关于中断的原理请参看《深入理解Linux中断机制》。所有中断和异常的入口函数都是通过DEFINE_IDTENTRY_IRQ或DEFINE_IDTENTRY(还有其它一些类似的宏)来定义的，其中一定会调用irqentry_exit。irqentry_exit又会根据寄存器状态来判断是返回到用户空间还是内核空间。如果是返回到用户空间则会调用irqentry_exit_to_user_mode，此函数的操作和从系统调用返回用户空间是相似的，就不再赘述了。如果是返回到内核空间则会调用irqentry_exit_cond_resched，调用此函数会先检测是否配置了CONFIG_PREEMPTION，没配置就不调用。CONFIG_PREEMPTION代表的是内核抢占，在有些场景中会说成抢占，但是要明白其代表的是内核抢占。
内核有时候为了同步，需要临时禁用抢占，这个禁用的是内核抢占，因为用户抢占永远可以。当代码配置了内核抢占时才有效。禁用抢占有引用计数，释放最后一个引用时才会重新开启内核抢占。禁用抢占和开启抢占分别用宏preempt_disable和preempt_enable。preempt_enable代表临界区的结束，会去检测是否需要调度。
禁用抢占临界区结束：
linux-src/include/linux/preempt.h
#define preempt_disable() \
do { \
preempt_count_inc(); \
barrier(); \
} while (0)
#define preempt_enable() \
do { \
barrier(); \
if (unlikely(preempt_count_dec_and_test())) \
__preempt_schedule(); \
} while (0)preempt_disable增加引用计数，preempt_enable减少引用计数并检测是否为0，如果为0则执行调度。
禁用软中断临界区结束：
linux-src/include/linux/bottom_half.h
static inline void local_bh_enable(void)
{
__local_bh_enable_ip(_THIS_IP_, SOFTIRQ_DISABLE_OFFSET);
}linux-src/kernel/softirq.c
void __local_bh_enable_ip(unsigned long ip, unsigned int cnt)
{
WARN_ON_ONCE(in_irq());
if (unlikely(!in_interrupt() && local_softirq_pending())) {
/*
* Run softirq if any pending. And do it in its own stack
* as we may be calling this deep in a task call stack already.
*/
do_softirq();
}
preempt_count_dec();
preempt_check_resched();
}linux-src/include/linux/preempt.h
#define preempt_check_resched() \
do { \
if (should_resched(0)) \
__preempt_schedule(); \
} while (0)在禁用软中断的过程中有可能其它地方已经触发了调度，因此在重新开启软中断的时候检测一下是否需要调度。
cond_resched调用点：
linux-src/include/linux/sched.h
#define cond_resched() ({ \
___might_sleep(__FILE__, __LINE__, 0); \
_cond_resched(); \
})
static inline int _cond_resched(void)
{
return __cond_resched();
}linux-src/kernel/sched/core.c
int __sched __cond_resched(void)
{
if (should_resched(0)) {
preempt_schedule_common();
return 1;
}
return 0;
}在很多比较耗时的内核操作中都会加上cond_resched调用，用来增加抢占调度的检测点，提高系统的响应性。
2.4 调度流程
前面讲了这么多触发调度的时机，现在该执行调度了。执行调度的总体逻辑是很简单的，就两个步骤：选择进程和切换进程。选择进程是一个很麻烦的过程，牵涉到调度类和调度算法，这个在下一节中讲。切换进程虽然不太麻烦，但是还是比较难以理解的，这个在2.7节中讲。执行调度的入口函数是__schedule，无论是从什么途径执行的调度，最终都要调用这个函数。
下面我们来看一下它的代码：
linux-src/kernel/sched/core.c
static void __sched notrace __schedule(unsigned int sched_mode)
{
struct task_struct *prev, *next;
struct rq_flags rf;
struct rq *rq;
int cpu;
cpu = smp_processor_id();
rq = cpu_rq(cpu);
prev = rq->curr;
next = pick_next_task(rq, prev, &rf);
if (likely(prev != next)) {
rq = context_switch(rq, prev, next, &rf);
} else {
__balance_callbacks(rq);
}
}代码经过删减，只留下了关键操作。首先是pick_next_task，选择下一个要执行的进程。然后是context_switch，切换进程。
2.5 调度算法
这节要讲的是pick_next_task，在讲之前我们要先讲一些概念逻辑。
内核中有调度类、调度策略、调度算法的概念，这三者是什么意思，又有什么关系呢？调度类代表的是进程对调度器的需求，主要是对调度紧迫性的需求。调度策略是调度类的子类，是对调度类的细分，是在同一个调度需求下的细微区别。调度算法是对调度类的实现，一个调度类一个调度算法。同一个调度类的调度策略是有很强的相似性的，所以在同一个算法中实现，对于它们不同的部分，算法再去进行区分。下面我们画个图来看一下Linux中的所有调度类、调度策略和调度算法。
Linux中一共有五个调度类，分别是stop(禁令调度类)、deadline(限时调度类)、realtime(实时调度类)、time-share(分时调度类)、idle(闲时调度类)。它们的调度紧迫性从上到下，依次降低。其中禁令调度类和闲时调度类有特殊的目的，仅用于内核，没有调度策略，由于这类进程在内核启动时就设置好了，一个CPU一个相应的进程，所以也不需要调度算法。另外三个调度类可用于用户空间进程，有相应的调度策略和调度算法，也有相应的API供用户空间来设置一个进程的调度策略和优先级。调度类之间的关系是有高类的进程可运行的情况下，绝对不会去调度低类的进程，只有当高类无Runnable的进程的时候才会去调度低类的进程。这里面也有一个例外就是内核为了防止实时进程饿死普通进程，提供了一个配置参数，默认值是实时进程如果已经占用了95%的CPU时间，就会把剩余5%的CPU时间分给普通进程。
禁令调度类是内核用来执行一些特别紧急的事物所使用的。禁令调度类的进程是内核在启动时就创建好的，一个CPU一个进程，名字叫做[migration/n]，n是CPU_ID，之后就不能再创建此类进程了。内核提供了一些接口可以向这些进程push work。调度均衡要迁移线程的时候会用到这类进程，所以它的名字叫做migration。
linux-src/include/linux/stop_machine.h
int stop_one_cpu(unsigned int cpu, cpu_stop_fn_t fn, void *arg); int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *arg); int stop_machine(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus); int stop_machine_cpuslocked(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus);
由于禁令调度类的进程优先级是最高的，只要此类进程变得Runnable了，就会立马抢占当前进程来运行，所以这几个接口的名字也都叫做stop_cpu、stop_machine之类的。大家不要望文生义地认为这几个接口能暂定CPU或者关机之类的。
限时调度类属于硬实时，适用于对调度时间有明确要求的进程。它只有一个调度策略，限时调度策略。一个进程必须通过系统调用才能把自己设置为限时调度策略，并且还要提供三个参数：运行周期、运行时间和截止时间。运行周期是说这个进程在多长时间内想要运行一次，运行时间是说这个进程每次想要运行多长时间，截止时间是说这个进程每次运行结束不能晚于什么时间。这三个参数都需要进程根据自己的实际情况向内核提供，而且不是说你提供了就一定能设置成功，内核还要检测与已有的限时调度类进程是否冲突，如果有冲突那就无法满足，就只能返回设置失败。还有一点是，运行时间是程序员要提供预估好的，如果程序实际运行时间超过了预估时间则会被切走，这可能会导致灾难性的后果。
实时调度类属于软实时，适用于那些只要可运行就希望立马能执行的进程，比如音视频的解码进程。实时调度类又分为两个调度策略，SCHED_FIFO和SCHED_RR。实时调度类的内部逻辑是让实时优先级大的进程先运行，只要有实时优先级大的进程可运行，就不会去调度实时优先级小的进程。当两个实时进程的优先级相同时，SCHED_RR和SCHED_FIFO这两个策略就有区别了，SCHED_FIFO进程如果抢占了CPU，它就会一直占着CPU，不会给同优先级的实时进程让CPU的，而SCHED_RR进程会在运行了一定的时间片之后主动让给同优先级的实时进程。
分时调度类是给广大的普通进程来用的，大家共同分享CPU。根据优先级的不同，可能有的进程分的多有的进程分的少，但是不会出现一个进程霸占CPU的情况。分时调度类下面有三个调度策略：SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE。它们的基本思想都是分时，但是略有不同，SCHED_BATCH进程希望减少调度次数，每次调度能执行的时间长一点，SCHED_IDLE是优先级特别低的进程，其分到的CPU时间的比例非常低，但是也总是能保证分到。分时调度类现在的算法叫做CFS(完全公平调度)，所以分时调度类也叫做公平调度类。
闲时调度类是给内核用的，当CPU没有其它进程可以执行的时候就会运行闲时调度类的进程。此类进程是在内核启动时就创建好的，一个CPU一个进程，此后就不能再创建此类进程了。闲时调度类的进程也叫做idle进程，它在内核中有些特殊的用途，比如CPUIdle的实现就和idle进程密切相关。
大家要注意，闲时调度类和分时调度类中SCHED_IDLE调度策略不是一回事，两者没有关系，大家不要弄混淆了。
系统为每个调度类都定义了一些标准的操作，我们来看一下：
linux-src/kernel/sched/sched.h
struct sched_class {
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*yield_task) (struct rq *rq);
bool (*yield_to_task)(struct rq *rq, struct task_struct *p);
void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
struct task_struct *(*pick_next_task)(struct rq *rq);
void (*put_prev_task)(struct rq *rq, struct task_struct *p);
void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
#ifdef CONFIG_SMP
int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
int (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
struct task_struct * (*pick_task)(struct rq *rq);
void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
void (*task_woken)(struct rq *this_rq, struct task_struct *task);
void (*set_cpus_allowed)(struct task_struct *p,
const struct cpumask *newmask,
u32 flags);
void (*rq_online)(struct rq *rq);
void (*rq_offline)(struct rq *rq);
struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
#endif
void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
void (*task_fork)(struct task_struct *p);
void (*task_dead)(struct task_struct *p);
void (*switched_from)(struct rq *this_rq, struct task_struct *task);
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
void (*prio_changed) (struct rq *this_rq, struct task_struct *task, int oldprio);
unsigned int (*get_rr_interval)(struct rq *rq, struct task_struct *task);
void (*update_curr)(struct rq *rq);
};每个调度类在实现自己的算法的时候都要实现这些函数指针，我们在讲到具体算法时再来讲解这些函数指针的含义。
下面我们来看一下pick_next_task的代码：
linux-src/kernel/sched/core.c
static struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
return __pick_next_task(rq, prev, rf);
}
static inline struct task_struct *
__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
const struct sched_class *class;
struct task_struct *p;
/*
* Optimization: we know that if all tasks are in the fair class we can
* call that function directly, but only if the @prev task wasn't of a
* higher scheduling class, because otherwise those lose the
* opportunity to pull in more work from other CPUs.
*/
if (likely(prev->sched_class <= &fair_sched_class &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = pick_next_task_fair(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto restart;
/* Assume the next prioritized class is idle_sched_class */
if (!p) {
put_prev_task(rq, prev);
p = pick_next_task_idle(rq);
}
return p;
}
restart:
put_prev_task_balance(rq, prev, rf);
for_each_class(class) {
p = class->pick_next_task(rq);
if (p)
return p;
}
/* The idle class should always have a runnable task: */
BUG();
}__pick_next_task进行了一个优化，因为大部分时间系统中主要存在的都是普通进程，所以先检测运行队列的运行数量和公平运行列队中的运行数量，如果相等的话就说明系统中目前只有普通进程，那么就可以直接调用pick_next_task_fair。接着就是主逻辑了，先从高调度类进行选择，如果有可运行的进程就直接返回，如果没有就去查询下一个调度类。最后一定能返回一个进程的，因为idle进程总是可运行的。
每个调度类的具体算法逻辑在后面的章节中讲解。
2.6 进程优先级
Linux上一共有5种调度类，其中禁令调度类和闲时调度类只在内核里使用，而且一个CPU只有一个线程，所以用不到进程优先级。限时调度类用的是进程设置的三个调度参数作为调度的依据，也用不到进程优先级。所以就只有实时调度类和分时调度类会用到进程优先级。它们使用优先级的方法也并不相同，我们在讲到具体算法时再讲。
由于历史原因，实时进程和普通进程的优先级并不是一个简单的数值，而是有好几个数值体系和变换规则，我们先来看一下设置进程调度策略和优先级的API。
#include <sched.h>
int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);
int sched_getscheduler(pid_t pid);
#include <sched.h>
int sched_setparam(pid_t pid, const struct sched_param *param);
int sched_getparam(pid_t pid, struct sched_param *param);
struct sched_param {
int sched_priority;
};
#include <unistd.h>
int nice(int inc);sched_setscheduler能同时设置实时调度类和分时调度类的调度策略和静态优先级，对于实时调度类，其静态优先级范围是1-99,99最大，对于分时调度类，其静态优先级必须设置为0，其动态优先级也就是nice需要通过nice接口来设置。sched_setparam可以设置实时进程的静态优先级，对于分时进程，其静态优先级必须为0。
我们再来看一下task_struct中记录优先级的字段。
linux-src/include/linux/sched.h
struct task_struct {
int prio;
int static_prio;
int normal_prio;
unsigned int rt_priority;
}一共有4个字段，rt_priority用来记录实时进程的用户空间的静态优先级，static_prio用来记录分时进程的用户空间的动态优先级并做了转换。然后rt_priority和static_prio一起转化为normal_prio(规范优先级)，此时实时进程和分时进程的优先级就在同一个数轴上了。最终起作用的是prio(动态优先级)，它的值默认等于normal_prio，一般不会变动。
下面我们画图来看一下进程的优先级转换：
在用户空间的时候，实时进程和普通进程(分时进程)共享同一个优先级数轴，叫静态优先级，范围是0-99，值越大优先级越高，实时进程占用1-99，普通进程占用0。普通进程自己又新开了一个数轴，叫动态优先级，也叫nice值，范围是 -20 - 19，值越低优先级越高。
到了内核空间的时候，实时进程有一个实时优先级，直接复制用户空间的静态优先级，普通进程有一个静态优先级，它是用户空间的nice值转换过来的，转换规则是nice+120。然后内核又定义了规范优先级，把它们都统一到同一个数轴上来。普通进程的规范优先级是直接复制其静态优先级，实时进程的规范优先级等于99减去它的实时优先级。在规范优先级的数轴上，所有进程都可以直接比较优先级了，值越小优先级越大。实时进程的规范优先级范围是0-99，但是由于它是从用户空间的优先级计算而来的，所以99这个值就用不到。
最后是动态优先级，对进程所有的处理都以动态优先级为准，动态优先级默认等于其规范优先级。以前的时候调度算法会去调整进程的动态优先级，现在不会再调了。现在只有使用了优先级继承锁的时候才会去调整进程的动态优先级。
下面让我们再画一个图总结一下：
对于禁令调度类、限时调度类和闲时调度类，它们用不到进程优先级，但是系统在规范优先级数轴上为它们提供了象征值，其动态优先级是对规范优先级的复制，也只有象征意义。有一个特殊的情况是分时调度类里面的SCHED_IDLE调度策略的进程，它的优先级无法在规范优先级数轴上体现出来，它的优先级是在CFS算法专门处理的，直接设置的调度权重，相当于是nice 26。
除了这些复杂的优先级体系之外，ps和top命令下的优先级体系也不相同。
ps命令优先级：
cls代表的是调度策略，含义如下：
TS SCHED_OTHER/SCHED_NORMAL
FF SCHED_FIFO
RR SCHED_RR
B SCHED_BATCH
IDL SCHED_IDLE
DLN SCHED_DEADLINE
NI代表的是nice值，范围：-20 – 19，-20最大，只有SCHED_NORMAL和SCHED_BATCH有意义。
RTPRIO代表的实时进程的用户空间优先级，范围：1 – 99，99最大，只有SCHED_FIFO和SCHED_RR有意义。
PRI，普通进程 pri = 19 - nice, 实时进程 pri = 40 + rtprio，值越大优先级越大，普通进程 0 – 39， 实时进程 41 – 139。
top命令优先级：
NI列是nice值，只对普通进程有效，对其它进程来说没有意义。
PR，普通进程 pr = 20 + nice，实时进程 pr = -1 - rt，rt是实时进程的用户空间优先级，PR值越小优先级越大，普通进程 0 – 39，实时进程 -2 – -100，-100会显示为rt，普通进程大于等于0，实时进程小于0。
2.7 进程切换
选择好下一个要执行的进程之后，就该切换进程了。切换进程一共分两步：一是切换用户空间，二是切换内核栈。下面我们来看一下代码(代码经过了高度删减)：
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next, struct rq_flags *rf)
{
switch_mm_irqs_off(prev->active_mm, next->mm, next);
switch_to(prev, next, prev);
return finish_task_switch(prev);
} switch_to(prev, next, prev);
barrier();
return finish_task_switch(prev);
}其中switch_mm_irqs_off是切换用户空间的，switch_to是切换内核栈的。
我们继续看切换用户空间是如何执行的。
linux-src/arch/x86/mm/tlb.c
void switch_mm_irqs_off(struct mm_struct *prev, struct mm_struct *next,
struct task_struct *tsk)
{
load_new_mm_cr3(next->pgd, new_asid, false);
}
static void load_new_mm_cr3(pgd_t *pgdir, u16 new_asid, bool need_flush)
{
unsigned long new_mm_cr3;
if (need_flush) {
invalidate_user_asid(new_asid);
new_mm_cr3 = build_cr3(pgdir, new_asid);
} else {
new_mm_cr3 = build_cr3_noflush(pgdir, new_asid);
}
write_cr3(new_mm_cr3);
}linux-src/arch/x86/include/asm/special_insns.h
static inline void write_cr3(unsigned long x)
{
native_write_cr3(x);
}
static inline void native_write_cr3(unsigned long val)
{
asm volatile("mov %0,%%cr3": : "r" (val) : "memory");
}切换进程地址空间就是给寄存器CR3赋予新的值。CR3中存放的是根页表的物理地址，build_cr3会把虚拟地址转化为物理地址。
下面我们继续看内核栈是如何切换的。
linux-src/arch/x86/include/asm/switch_to.h
#define switch_to(prev, next, last)
\do {
\ ((last) = __switch_to_asm((prev), (next)));
\} while (0)linux-src/arch/x86/entry/entry_64.S
SYM_FUNC_START(__switch_to_asm) /* * Save callee-saved registers * This must match the order in inactive_task_frame */ pushq %rbp pushq %rbx pushq %r12 pushq %r13 pushq %r14 pushq %r15 /* switch stack */ movq %rsp, TASK_threadsp(%rdi) movq TASK_threadsp(%rsi), %rsp #ifdef CONFIG_STACKPROTECTOR movq TASK_stack_canary(%rsi), %rbx movq %rbx, PER_CPU_VAR(fixed_percpu_data) + stack_canary_offset #endif #ifdef CONFIG_RETPOLINE /* * When switching from a shallower to a deeper call stack * the RSB may either underflow or use entries populated * with userspace addresses. On CPUs where those concerns * exist, overwrite the RSB with entries which capture * speculative execution to prevent attack. */ FILL_RETURN_BUFFER %r12, RSB_CLEAR_LOOPS, X86_FEATURE_RSB_CTXSW #endif /* restore callee-saved registers */ popq %r15 popq %r14 popq %r13 popq %r12 popq %rbx popq %rbp jmp __switch_to SYM_FUNC_END(__switch_to_asm)
切换内核栈是内核中最难理解的地方之一，难以理解的有两点：一是进程执行是如何切换的；二是switch_to宏为何有三个参数，第三个参数为啥又是prev。
我们先来解释第一个点，进程执行是如何切换的，先来画个图看一下：
如图中所示一样，每个线程都有一个线程栈，代表线程的执行，CPU只有一个(线程切换前后是同一个CPU)。CPU在哪个线程栈上运行，就是在运行在哪个线程，而线程栈上记录的就是线程的运行信息，所以这个线程就可以继续运行下去了。如果从单个进程的角度来看，从switch_to开始，我们的进程就暂停运行了，我们的进程就一直在这等，等到我们被唤醒并调度执行才会继续走下去。如果从CPU的角度来看，switch_to切换了内核栈，就在新的线程上运行了，函数返回的时候就会按照内核栈的调用地址返回，执行的就是新的代码了，就不是原来的代码了。当内核栈不停地返回，就会返回到用户空间，内核栈的底部记录的有用户空间的调用信息，由于前面已经切换了用户空间，所以程序就能返回到之前用户空间进入内核的地方。
我们再来说第二点，switch_to宏为啥有三个参数，为啥这么难以理解呢？这是因为switch_to实际上包含了三个进程：一个是我们自己prev，一个是即将要切换的进程next，一个是我们下次是从哪个进程切换过来的，我们把这个进程叫做from。而switch_to通过复用prev变量而把from变量给省略了，这就导致了理解上的混乱。我们来修改一下代码，把switch_to宏给展开，并把prev改名为curr，把from变量也给显式地定义出来，来看看效果怎么样。
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *curr,
struct task_struct *next, struct rq_flags *rf)
{
switch_mm_irqs_off(curr->active_mm, next->mm, next);
struct task_struct *from = NULL;
from = __switch_to_asm(curr, next);
barrier();
return finish_task_switch(from);
}这下就好理解多了。从单个进程的角度来看，__switch_to_asm会切换到next进程去执行，我们的进程就休眠了。很久以后我们的进程醒来又重新开始执行了，__switch_to_asm返回的是把CPU让给我们的那个进程。从CPU的角度来看__switch_to_asm函数前半程在curr进程运行，后半程在next进程运行。由于切换了内核栈，所以from、curr、next这三个变量也变了，它们是不同栈上的同名的局部变量，它们的内存地址是不一样的。当前进程中的curr值会被作为next进程中的from值返回，所以在next进程中就知道了是从哪里切换过来的了。
__switch_to_asm中最关键的两句代码我们再拿出来分析一下。
linux-src/arch/x86/entry/entry_64.S
/* switch stack */ movq %rsp, TASK_threadsp(%rdi) movq TASK_threadsp(%rsi), %rsp
linux-src/include/generated/asm-offsets.h
#define TASK_threadsp 3160 /* offsetof(struct task_struct, thread.sp) */
每个进程的内核栈的栈指针都在task_struct中的thread.sp保存着，第一个mov语句是把当前进程的栈指针保存起来以备后面使用，第二个mov语句是加载next进程的栈指针，这条指令执行之后就意味着进程切换成功了。后面还有一些语句用来加载之前保存在栈上的寄存器信息。
如果大家对前面修改的代码感兴趣，想打log验证一下，可以参考下面我加的log。
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *curr,
struct task_struct *next, struct rq_flags *rf)
{
switch_mm_irqs_off(curr->active_mm, next->mm, next);
struct task_struct *from = NULL;
if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {
pr_err("AAAAAA, -------------------------------------------");
pr_err("AAAAAA, start");
pr_err("AAAAAA, &curr:%p", &curr);
pr_err("AAAAAA, &next:%p", &next);
pr_err("AAAAAA, &from:%p", &from);
pr_err("AAAAAA, from:%p", from);
pr_err("AAAAAA, curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);
pr_err("AAAAAA, next:%p, pid:%d, comm:%s", next, next->pid, next->comm);
dump_stack();
pr_err("AAAAAA, -------------------------------------------");
}
from = __switch_to_asm(curr, next);
barrier();
if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {
pr_err("AAAAAA, &curr:%p", &curr);
pr_err("AAAAAA, &next:%p", &next);
pr_err("AAAAAA, &from:%p", &from);
pr_err("AAAAAA, from:%p, pid:%d, comm:%s", from, from->pid, from->comm);
pr_err("AAAAAA, curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);
pr_err("AAAAAA, next:%p, pid:%d, comm:%s", next, next->pid, next->comm);
dump_stack();
pr_err("AAAAAA, end");
pr_err("AAAAAA, -------------------------------------------");
}
return finish_task_switch(from);
}这里面有两个技巧，一是使用jiffies % 1000 == 0来减少log的数量，内核中进程切换非常频繁，过多的log往往难以分析，二是使用1 == smp_processor_id()把log锁定在一个CPU上，不然的话多个CPU上的切换log会相互干扰，难以理清，我们只看一个CPU上的log，就会发现逻辑很清晰。
下面我画了一个图模拟了一下单个CPU上的三个进程之间的切换，大家来看一下：
有三个进程pid 分别为1、3、5在CPU0上进行切换，切换顺序是1->3->5->1->5->3->1。图中是按照我修改之后的代码来画的，有from、curr、next三个指针变量。可以看到一个进程它必须先切走才能切回，因为不切走怎么能切回来呢。但是对于刚创建的进程它是没有切走过的，于是内核会为它伪造内核栈也就是切点，使得它可以切回。正常的内核栈是__schedule函数调用了__switch_to_asm函数，__switch_to_asm函数还会返回到__schedule函数。伪造的内核栈是仿佛ret_from_fork调用了__switch_to_asm函数，__switch_to_asm函数在返回的时候就会返回到ret_from_fork函数来执行。对于内核线程和普通线程伪造的栈上的数据是不一样的，对于普通线程其rbx寄存器对应的位置是0，对于内核线程其rbx寄存器对应的位置是入口函数的指针，具体来说是kthread。ret_from_fork先调用schedule_tail，然后根据rbx的不同，其为0时说明是普通进程，调用syscall_exit_to_user_mode，不为0时说明是内核线程，调用rbx也就是kthread。kthread函数一般是不会返回的，但是如果其中调用了kernel_execve建立了用户空间也可以返回，返回到ret_from_fork中后会调用syscall_exit_to_user_mode。
对于这幅图大家可以只看一个进程的执行情况，按照一个进程pid从上往下看就可以了。也可以看整个CPU的执行情况，按照红色箭头的标号顺序来看，注意观察from、curr、next三个值的变化。
Tags：
很赞哦！ ()
随机图文
Linux 中断所有知识点
GIC，Generic Interrupt Controller。是ARM公司提供的一个通用的中断控制器。主要作用为：接受硬件中断信号，并经过一定处理后，分发给对应的CPU进行处理。 当前GIC 有四个版本，GIC v1~v4, 本文主要介绍GIC v3控制器。
一文搞定 | Linux共享内存原理
在Linux系统中，每个进程都有独立的虚拟内存空间，也就是说不同的进程访问同一段虚拟内存地址所得到的数据是不一样的，这是因为不同进程相同的虚拟内存地址会映射到不同的物理内存地址上。 但有时候为了让不同进程之间进行通信，需要让不同进程共享相同的物理内存，Linux通过 共享内存 来实现这个功能。下面先来介绍一下Linux系统的共享内存的使用。
深入理解CPU的调度原理
前言软件工程师们总习惯把OS（Operating System，操作系统）当成是一个非常值得信赖的管家，我们只管把程序托管到OS上运行，却很少深入了解操作系统的运行原理。确实，OS作为一个通用的
Linux 内核的网络协议栈
本文主要记录 Linux 内核网络协议栈的运行原理
文章评论
本站推荐
猜你喜欢
