|
在 Linux 这个庞大而精妙的操作系统世界里，就像一座繁华的都市，进程如同忙碌的市民，而进程调度则是这座都市的交通指挥中心。它有条不紊地安排着每个进程对 CPU 资源的使用，决定着哪些进程可以先行，哪些需要等待。今天，我们就一同深入探索 Linux 进程调度这一内核核心机制，揭开它是如何让整个系统高效、稳定且公平地运行的神秘面纱。 一、简介1.1进程调度概述进程调度是操作系统最重要的内容之一，也是学习操作系统的重点和难点。关于进程调度，我们首先就会问出一些问题，什么是进程调度，为什么要进程调度，如何进行调度。下面我们用一幅图把这些问题关联起来：  这张图把进程调度的所有问题和知识点都关联了起来，本文后面所有的内容都是对这张图的解释和扩展延伸，下面让我们来一一讲解。 ⑴什么是调度 什么是调度？调度是CPU资源管理器。操作系统的作用之一就是系统资源管理器。CPU是计算机系统中最重要的资源，当然也要管理。所有进程的运行都需要CPU，对CPU该如何管理呢？对于直接共享型的事物，我们有两种管理方法：一种是时间分割管理，另一种是空间分割管理。由于CPU自身的特性，没有空间分割相似性，只有时间分割相似性，所以我们只能对CPU进行时间分割管理。对CPU进行时间分割管理的具体做法就叫做进程调度。 那么调度的是什么呢？进程调度，调度的当然是进程啦，也对也不对。我们知道进程是资源分配的单位，线程是执行的单位。早期的时候没有多线程，进程就是线程，线程就是进程，所以此时进程调度调度的是进程。但是当有了多线程之后，线程变成了执行的单位，进程不再是执行的单位，进程调度调度的就是线程了。不过由于历史原因，大家都习惯叫进程调度，所以现在这个领域的名称还是叫进程调度。后文中说到调度进程的地方都是调度的线程，由于习惯问题，我们还说调度进程不说调度线程，请大家要注意。 对线程的调度可以有两种方式：一种是直接调度线程，不考虑它们所属的进程，这种方式叫做直接调度或者一级调度；另一种是先调度进程，再在进程内部调度线程，这种方式叫做间接调度或者二级调度。POSIX规定，操作系统可以选择这两种方式中的任何一种都行。Linux选择的是一级调度，为什么会这么选择呢？主要是为了提高进程的并发性，充分利用多CPU多核的优势。如果使用二级调度的话，看似每个进程之间都公平了，但是有些进程的计算量比较大，就无法通过多开线程提高自己的性能，这样对系统整体的性能是有害的，也不利用发挥计算机多CPU的优势。一级调度看似对有些进程不公平，但是计算量小的进程少开线程，计算量大的进程多开线程，相对还是很公平的。 就像国家希望每个企业都做大做强，但是同时也会反垄断一样。Linux也推出了cgroup组调度机制，来限制某个或者某一类进程对CPU资源的过度占用。本文中不讲cgroup组调度机制，后文的讲解都是假设没有cgroup组调度。 ⑵为什么要调度 我们知道了什么是调度，那么为什么要调度呢，没有调度会怎么样呢？最早的计算机是没有调度的，程序只能一个一个地运行，一个进程死亡之后才能去运行下一个进程。这里面首先存在的问题就是我们没法同时运行多个进程。其次就算我们不需要同时运行多个进程，程序在运行的过程中如果要等IO，CPU就只能空转，这也十分浪费CPU资源。 于是最早的多任务——协作式多任务诞生了，当程序由于要等IO而阻塞时就会去调度执行其它的进程。但是协作式多任务存在着很大的问题，就是每个进程运行的时间片长短是不确定的，而且是很偶然很随机的。如果一个进程它一直在做运算就是不进行IO操作，那么它就会一直霸占CPU。 针对这个问题，当时想出的方法是道德解决方案。内核向进程提供系统调用sched_yield，它会使进程主动放弃CPU让其它进程来执行。然后要求所有的程序员在程序中合适的地方尽量多地加入sched_yield调用。这个方法在当时是管用的，因为当时计算机的使用者(同时也是程序员)仅限于少数科研机构和政府机关的部分人员，一台电脑的共同使用者都认识，面子上还得过得去。 后来随着计算机的普及，以及计算机的使用者和程序员这两个角色的分离，主要靠道德约束的协作式多任务已经行不通了，我们需要强制性多任务，也就是抢占式多任务。抢占式多任务使得每个进程都可以相对公平地平分CPU时间，如果一个进程运行了过长的时间就会被强制性地调度出去，不管这个进程是否愿意。 有了抢占式多任务，我们在宏观上不仅可以同时运行多个进程，而且它们会一起齐头并进地往前运行，不会出现某个进程被饿死的情况，这样我们使用电脑的体验就非常完美了。抢占式多任务和协作式多任务不是对立的，它们是相互独立的，可以同时存在于系统中。 抢占又分为用户抢占和内核抢占。由于抢占对进程来说是异步的，进程被抢占时不一定运行在什么地方，有可能运行在用户空间，也有可能运行在内核空间(进程通过系统调用进入内核空间)。如果抢占点是在用户空间，那么抢占就是安全的，如果在内核空间就不一定安全，这是为什么呢？因为对于用户空间来说，如果抢占会导致线程同步问题，那么用户空间有责任使用线程同步机制来保护临界区，只要用户空间做好同步就不会出问题。 如果内核也做好了同步措施，内核抢占也不会出问题，但是内核最初的设计就没有考虑内核抢占问题，所以刚开始的时候内核是不能抢占的。后来内核开发者对内核进行了完善，把内核所有的临界区都加上了同步措施，然后内核就是可抢占的了。内核能抢占了不代表内核一定会抢占，内核会不会抢占由config选项控制，可以开启也可以关闭，因为内核抢占还会影响系统的响应性和性能。 开启内核抢占会提高系统的响应性但是会降低一点性能，关闭内核抢占会降低系统的响应性但是会提高一点性能。因此把内核抢占做成配置项，可以让大家灵活配置。服务器系统一般不需要与用户交互，所以会关闭内核抢占来提高性能，桌面系统会开启内核抢占来提高系统的响应性，来增加用户体验。 现在我们再来看一下为什么要调度。因为如果没有调度的话，就不能实现多任务，一次就只能运行一个程序，我们使用电脑的体验就会大大降低。有了调度就有了多任务，我们就能同时在电脑上做很多事情，使用体验就会非常好。 ⑶为什么能调度 我们再来看看为什么能调度呢。我们把协作式多任务叫做主动调度，抢占式多任务叫做被动调度。为什么能调度分为两部分：为什么能触发调度和为什么能执行调度。对于主动调度，调度是进程主动触发的，这个是肯定能的。对于被动调度，在图灵机模型中是做不到的，因为图灵机是一条线性一直往前走的，进程在执行时，进程要是不主动，是不可能跳到其它进程来执行的。 被动调度能做到的原因关键就在于中断机制，因为中断是强行在正常的执行流中插入了一段代码，它能改变后续代码的走向。有了中断机制，我们就可以创建一个定时器中断，以固定的时间间隔比如每10ms来触发中断，检测进程是否运行时间过长，如果过长就触发调度。这样任何进程都不可能霸占CPU，所以进程都能公平地共享CPU时间。  可以看到在纯图灵机模型中，进程如果不主动进行调度，是没有外力强迫进程进行调度的，进程就能一直霸占CPU。有了中断机制之后，在中断的处理中可以触发调度，在中断返回的点可以执行调度，这样就可以避免进程霸占CPU了。 前面说的是为何能触发进程调度，主动调度是进程自己触发的，被动调度是在中断中触发的。现在来看看为何能执行调度，执行调度包括两部分：选择进程和切换进程。选择进程是纯软件的，肯定能实现。切换进程是怎么切换呢？一个进程执行的好好的，怎么就切换了呢，需不需要硬件的支持呢？进程切换主要是切换执行栈和用户空间，这两个都需要用到CPU特定的指令。 ⑷何时调度 我们前面已经讲了主动调度(协作式多任务)和被动调度(抢占式多任务)。 对于主动调度，触发调度和执行调度是同步的、一体的，触发即执行。主动调度发生的时机有IO等待、加锁失败等各种阻塞操作以及用户空间主动调用sched_yield。 对于被动调度，触发调度和执行调度是异步的、分离的，触发调度并不会立马执行调度，而是做个需要调度的标记，然后在之后的某个合适的地方会检测这个标记，如果被设置就进行调度。触发调度的点有：在定时器中断中发现当前进程超时了，在唤醒进程时发现新进程需要抢占当前进程，在迁移进程时发现新进程需要抢占当前进程，在改变进程优先级时发现新进程需要抢占当前进程。 其中第一个触发点是当前进程需要被抢占，它是用来保证公平调度，防止进程霸占CPU的，后三个触发点是新进程需要抢占当前进程，它是用来提高系统响应性的。执行调度的点有：系统调用完成之后即将返回用户空间，中断完成之后即将返回用户空间，如果开启了内核抢占的话则还有,中断完成之后即将返回内核,如果中断发生在禁止抢占临界区中，那么中断完成之后返回内核是不会执行调度的，而是会在临界区结束的时候执行调度。  系统调用完成之后即将返回用户空间和中断完成之后即将返回用户空间，是非常好的执行进行调度的点，也就是此图中的三个箭头的地方。CPU异常在意义上不是系统调用，但是在形式上和逻辑上相当于是系统调用。   中断发生在内核空间的场景，如果开启了内核抢占，如果被抢占的内核代码不是在禁用抢占临界区，中断返回时是执行调度的点。如果被抢占的内核代码在禁用抢占临界区中，在执行调度的点被推迟到了临界区的出口处。 ⑸如何调度 现在到了执行调度的时刻了。执行调度分为两步：一是选择下一个要执行的进程，二是切换进程。选择下一个要执行的进程，这就是调度算法了。首先调度算法只能从Runnable的进程中进行选择，不能选择Blocked进程，因为选择了也没有意义。其次算法还要区分进程类型，比如普通进程与实时进程，肯定要优先选择实时进程，在同一类型的进程中还要有具体的算法来决定到底选择哪个进程。在Linux中一共把进程分为了5类，每一类都有一个具体的算法。类之间的关系是优先选择高类的进程，只有当高类没有Runnable进程时才会去选择低类进程。 进程选择好了之后就要切换进程了。切换进程分两步：第一步是切换用户空间，第二步是切换执行栈(线程栈)。如果要切换的两个线程属于同一个进程就不需要切换用户空间了。切换用户空间是一个CPU架构相关的事情，在x86 CPU上是给CR3寄存器赋值新进程的页表树的根指针。 此时切换的执行栈是线程的内核栈，执行栈代表的是当前线程的执行情况，切换执行栈就是切换线程。线程的用户栈信息都在内核栈里保存着。切换完内核栈之后，线程继续执行就会返回用户空间，由于此时用户空间已经切换完成，内核栈上也保存着用户栈的信息，所以线程能返回到正确的用户空间线程上去。下面我们画个图来看一下：  对于一个CPU来说，永远只有一个当前进程在运行，当执行进程调度时，需要从其它进程中选择一个进程，把它旋转到最下方作为当前进程，它就开始运行了。 ⑹调度均衡 前面所说的都是针对一个CPU的情况，对于多个CPU来说，每个CPU也是这样的逻辑。但是有一点不同的是，如果一个系统上的多个CPU忙的忙死闲的闲死，显然不太好，因此多个CPU之间会进行调度均衡。调度均衡可以分为个体均衡和总体均衡。个体均衡是从进程的角度出发选择到一个相对清闲的CPU上去运行。总体均衡是从CPU的角度出发如何从别的CPU上拉取一些进程到自己这来执行，使得所有CPU的工作量尽量平均。 个体均衡的触发点有三个：一是新进程刚创建时，二是进程要执行新程序时，三是进程被唤醒时，在这三个点进程都可以选择去哪个CPU的运行队列上去等待执行。在个体均衡下，每个进程都尽量选择相对清闲的CPU，所以所有CPU的负载应该还是会比较均衡的。但是时间长了可能还是会出现负载不均衡的情况，此时就要进行总体均衡了。总体均衡的触发点有三个：一是CPU即将idle前会去找到最忙的CPU然后拉取一些任务过来；二是定时器中断的周期性检测，会检查是否所有的CPU都一样忙，如果忙闲差别太大就会进行进程迁移，使得所有CPU忙闲程度接近；三是在idle进程中如果CPU发现自己太忙而有的CPU在idle就会唤醒那个CPU进行负载均衡。 1.2进程调度框架前面我们对进程调度的概念和逻辑进行了讲解，现在我们来看一下Linux上进程调度的框架结构。本章只讲总体框架，不讲具体算法，具体算法在后面的章节中讲。 ⑴调度队列 我们先来看一下进程的状态转换图：  处于就绪(Runnable)状态的进程可以被调度到CPU上去执行。但是处于就绪状态的进程可能不止一个，所以我们需要一个运行队列来安放所有就绪的进程，由于CPU也不止一个，所以我们需要NR_CPU个运行队列。 我们看一下调度队列的定义(代码经过了高度删减)：linux-src/kernel/sched/sched.h linux-src/kernel/sched/core.c 内核定义了一个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。 ⑵进程唤醒 进程是怎么被放入运行队列的呢？都是通过进程唤醒来放入的，包括新创建的进程也是。新建唤醒和阻塞唤醒的代码不太一样，下面我们分别来看一下。 我们先来看一下新建唤醒的代码：linux-src/kernel/sched/core.c 在fork中会调用此函数唤醒新创建的进程，把它放入到运行队列中等待被调度。此函数会先调用select_task_rq来选择自己要去哪个CPU的rq上去，然后调用activate_task把进程加入到相应的运行队列上，最后调用check_preempt_curr看一下是否需要抢占，如果需要就触发抢占。select_task_rq的逻辑我们在调度均衡中讲，check_preempt_curr的逻辑我们在下一节的被动调度中讲。 我们再来看一下阻塞唤醒的代码：linux-src/kernel/sched/core.c 阻塞唤醒的核心逻辑是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是一样的。 ⑶调度时机 进程放入运行队列之后就等着被调度到CPU上去运行了。但是当前进程正在使用着CPU，它什么时候能把CPU让给其它进程去运行呢？有两种情况：一是当前进程主动让出CPU，这叫主动调度；二是当前进程被动让出CPU，这叫被动调度，也就是进程抢占。 主动调度：主动调度又可以分为自愿性主动调度和非自愿性主动调度。自愿性主动调度是指进程主动调用sched_yield让出CPU，进程本身还会回到运行队列中去等待下次调度。如果运行队列中没有其它进程的话，此进程还会继续运行。非自愿性主动调度是指进程运行时遇到了无法继续运行的情况，只能进行调度让其它进程运行。进程无法继续运行的情况有加锁失败、要读的文件现在不在内存中、进程死亡等。 下面我们来看一个非自愿性主动调度的例子，信号量获取失败时的操作：linux-src/kernel/locking/semaphore.c 先定义一个等待项，把自己加入到信号量的等待列表中，然后调用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 在低精度定时器、高精度定时器与固定tick、动态tick的不同组合下，定时器中断触发的方式是不同的，但是最终都会调用scheduler_tick。scheduler_tick会调用当前进程的调度类的task_tick函数，此函数根据具体的情况可能会触发调度。task_tick函数的实现细节我们在具体的调度算法中再讲。 唤醒进程有新建唤醒和阻塞唤醒，它们都有可能触发调度。我们来看一下：linux-src/kernel/sched/core.c 在低精度定时器、高精度定时器与固定tick、动态tick的不同组合下，定时器中断触发的方式是不同的，但是最终都会调用scheduler_tick。scheduler_tick会调用当前进程的调度类的task_tick函数，此函数根据具体的情况可能会触发调度。task_tick函数的实现细节我们在具体的调度算法中再讲。 唤醒进程有新建唤醒和阻塞唤醒，它们都有可能触发调度。我们来看一下：linux-src/kernel/sched/core.c linux-src/include/linux/sched.h 可以看到无论是新建唤醒还是阻塞唤醒，最终都是调用check_preempt_curr函数来处理的。如果被唤醒的进程和当前进程是同一个调度类的则会调用调度类的函数来处理，这个逻辑我们在具体调度类中再讲。如果被唤醒的进程比当前进程的调度类高，则会触发调度。resched_curr函数最终会在thread_info的flag中设置TIF_NEED_RESCHED标记。 下面我们再来看一下执行调度的点，以x86为例。 系统调用返回用户空间：linux-src/arch/x86/entry/common.c linux-src/kernel/entry/common.c 可以看到系统调用完成之后返回用户空间之前会检测thread_info flag中的_TIF_NEED_RESCHED，如果设置了就会执行调度。 中断返回用户空间或者内核空间：linux-src/arch/x86/include/asm/idtentry.h linux-src/kernel/entry/common.c 所有中断和异常的入口函数都是通过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 preempt_disable增加引用计数，preempt_enable减少引用计数并检测是否为0，如果为0则执行调度。 禁用软中断临界区结束：linux-src/include/linux/bottom_half.h linux-src/kernel/softirq.c linux-src/include/linux/preempt.h 在禁用软中断的过程中有可能其它地方已经触发了调度，因此在重新开启软中断的时候检测一下是否需要调度。 cond_resched调用点：linux-src/include/linux/sched.h linux-src/kernel/sched/core.c 在很多比较耗时的内核操作中都会加上cond_resched调用，用来增加抢占调度的检测点，提高系统的响应性。 ⑷调度流程 前面讲了这么多触发调度的时机，现在该执行调度了。执行调度的总体逻辑是很简单的，就两个步骤：选择进程和切换进程。选择进程是一个很麻烦的过程，牵涉到调度类和调度算法，这个在下一节中讲。切换进程虽然不太麻烦，但是还是比较难以理解的，这个在2.7节中讲。执行调度的入口函数是__schedule，无论是从什么途径执行的调度，最终都要调用这个函数。 下面我们来看一下它的代码：linux-src/kernel/sched/core.c 代码经过删减，只留下了关键操作。首先是pick_next_task，选择下一个要执行的进程。然后是context_switch，切换进程。 ⑸调度算法 这节要讲的是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 由于禁令调度类的进程优先级是最高的，只要此类进程变得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 每个调度类在实现自己的算法的时候都要实现这些函数指针，我们在讲到具体算法时再来讲解这些函数指针的含义。下面我们来看一下pick_next_task的代码：linux-src/kernel/sched/core.c __pick_next_task进行了一个优化，因为大部分时间系统中主要存在的都是普通进程，所以先检测运行队列的运行数量和公平运行列队中的运行数量，如果相等的话就说明系统中目前只有普通进程，那么就可以直接调用pick_next_task_fair。接着就是主逻辑了，先从高调度类进行选择，如果有可运行的进程就直接返回，如果没有就去查询下一个调度类。最后一定能返回一个进程的，因为idle进程总是可运行的。 ⑹进程优先级 Linux上一共有5种调度类，其中禁令调度类和闲时调度类只在内核里使用，而且一个CPU只有一个线程，所以用不到进程优先级。限时调度类用的是进程设置的三个调度参数作为调度的依据，也用不到进程优先级。所以就只有实时调度类和分时调度类会用到进程优先级。它们使用优先级的方法也并不相同，我们在讲到具体算法时再讲。 由于历史原因，实时进程和普通进程的优先级并不是一个简单的数值，而是有好几个数值体系和变换规则，我们先来看一下设置进程调度策略和优先级的API。 sched_setscheduler能同时设置实时调度类和分时调度类的调度策略和静态优先级，对于实时调度类，其静态优先级范围是1-99,99最大，对于分时调度类，其静态优先级必须设置为0，其动态优先级也就是nice需要通过nice接口来设置。sched_setparam可以设置实时进程的静态优先级，对于分时进程，其静态优先级必须为0。 我们再来看一下task_struct中记录优先级的字段：linux-src/include/linux/sched.h 一共有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。 ⑺进程切换 选择好下一个要执行的进程之后，就该切换进程了。切换进程一共分两步：一是切换用户空间，二是切换内核栈。下面我们来看一下代码(代码经过了高度删减)：linux-src/kernel/sched/core.c 其中switch_mm_irqs_off是切换用户空间的，switch_to是切换内核栈的。 我们继续看切换用户空间是如何执行的，linux-src/arch/x86/mm/tlb.c linux-src/arch/x86/include/asm/special_insns.h 切换进程地址空间就是给寄存器CR3赋予新的值。CR3中存放的是根页表的物理地址，build_cr3会把虚拟地址转化为物理地址。 下面我们继续看内核栈是如何切换的。 linux-src/arch/x86/include/asm/switch_to.h linux-src/arch/x86/entry/entry_64.S 切换内核栈是内核中最难理解的地方之一，难以理解的有两点：一是进程执行是如何切换的；二是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变量也给显式地定义出来，来看看效果怎么样。 这下就好理解多了。从单个进程的角度来看，__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 linux-src/include/generated/asm-offsets.h 每个进程的内核栈的栈指针都在task_struct中的thread.sp保存着，第一个mov语句是把当前进程的栈指针保存起来以备后面使用，第二个mov语句是加载next进程的栈指针，这条指令执行之后就意味着进程切换成功了。后面还有一些语句用来加载之前保存在栈上的寄存器信息。 如果大家对前面修改的代码感兴趣，想打log验证一下，可以参考下面我加的log。 这里面有两个技巧，一是使用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三个值的变化。 二、Linux进程状态与优先级2.1进程状态详解Linux 进程有多种状态，常见的状态包括：
进程状态之间可以相互转换。一般来说，进程可能从可执行状态（R）进入睡眠状态（S 或 D），当等待的事件发生时，又从睡眠状态转换回可执行状态。如果进程收到暂停信号，会从可执行状态转换为暂停状态（T），收到继续执行的信号后再转换回可执行状态。当进程完成任务后，会从可执行状态转换为退出状态（Z 或 X）。 2.2优先级分类Linux 提供两种优先级：普通进程优先级和实时进程优先级。 ⑴实时进程优先级： 实时优先级采用两种调度算法：SCHED_FIFO（先入先出调度算法）和 SCHED_RR（时间片轮询调度算法）。 实时优先级只有静态优先级，不会调整优先级，默认优先级为 0 - 99（MAX_RT_PRIO = 100）。nice 值只影响 100 ~ 100 + 40 的进程优先级。 对于 SCHED_FIFO 算法，只有当进程执行完毕才能轮到其他进程执行；对于 SCHED_RR 算法，一旦时间片消耗完，则将该进程放到队列末端，其他进程才能执行。 ⑵普通进程优先级 普通优先级采用的调度算法是 SCHED_NORMAL（CFS 调度器实现）。 普通优先级根据动态优先级调度，动态优先级由静态优先级调整而来。静态优先级由内核隐藏，但可以由 nice 值计算得到：static_prio = MAX_RT_PRIO（默认 100）+ nice + 20。nice 取值范围是 -20 ~ 19，所以静态优先级为 100 ~ 139。 进程时间片也是由静态优先级得到。如果静态优先级小于 120，时间片为 (140 - static_prio) * 20；如果静态优先级大于等于 120，时间片为 (140 - static_prio) * 5。 动态优先级主要考虑静态优先级和进程平均运行时间 bouns 值，计算公式为：dynamic_prio = max (100, min (static_prio - bouns + 5, 139))。当 bouns 值大于 5 表示优先级提高，小于 5 时优先级变低。Linux 内核会根据进程的平均运行时间动态改变进程的动态优先级。一般来说，交互式进程的平均运行时间比较长，因此 Linux 内核会奖励从而增加 bouns 的值。 三、Linux进程调度算法3.1普通进程调度算法⑴时间片分配与微调函数 普通进程的时间片分配方式较为复杂，它是根据静态优先级来计算初始时间片。静态优先级由内核隐藏，但可以通过 nice 值计算得到，公式为 static_prio = MAX_RT_PRIO（默认 100）+ nice + 20，其中 nice 取值范围是 -20 ~ 19。如果静态优先级小于 120，时间片为 (140 - static_prio) * 20；如果静态优先级大于等于 120，时间片为 (140 - static_prio) * 5。 Linux 用函数 goodness () 来衡量一个处于可运行状态的进程值得运行的程度，该函数会对权重进行微调，以缩小进程实际使用时间片的差异。例如，在一些复杂的多任务环境中，通过 goodness 函数的微调作用，可以使不同优先级的进程在时间片分配上更加合理，避免某些进程长时间占用 CPU 资源而其他进程得不到执行机会的情况。 ⑵多种调度算法特点分析 ①先来先服务算法（FCFS） 原理：依据进程进入就绪状态的先后顺序排列，非抢占式不公平。当一个进程进入就绪队列后，只有当前正在运行的进程停止执行，才会选择在就绪队列中存在时间最长的进程运行。 优点：易于理解，便于实现，只需一个就绪队列。 缺点：平均等待时间波动大，例如短进程排在长进程后；I/O 与 CPU 资源利用率低，CPU 密集型进程会导致 I/O 设备闲置时，I/O 密集型进程也等待。 适用场景：适用于一些对执行顺序有严格要求的场景，比如某些批处理任务。 ②最短作业优先算法（SJF） 原理：预知就绪队列中执行时间最短进程占用 CPU 进入运行状态，非抢占式不公平。系统会从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 优点：相对于 FCFS 提高了平均周转时间。 缺点：可能导致饥饿；对长作业不公平；需要预知未来，即预估下一个 CPU 计算的持续时间，通常是询问用户或用历史的执行时间来预估未来的执行时间。 适用场景：适用于对响应时间要求较高的场景，但由于其缺点，实际应用中需要谨慎考虑。 ③最高响应比优先法（HRRN） 原理：响应比 R 定义为作业等待时间 / 作业运行所需时间，响应比大的进程优先，非抢占式不公平。该算法同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 优点：同时考虑了等待时间和执行时间，既优先考虑短作业，也防止长作业无限等待的饥饿。 缺点：每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行，这样会增加系统开销。另外，采用 HRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。 适用场景：是对 FCFS 方式和 SJF 方式的一种综合平衡，适用于对作业响应时间和执行时间都有一定要求的场景。 ④时间片轮转算法（RR） 原理：将所有就绪进程排成一个队列，按照时间片轮转调度，用完时间片的进程排到队列末尾，抢占式公平。每次从就绪队列中选择队首的进程，让它执行一个时间片长度的时间，执行完毕之后将此程序放到队列的队尾，再次取新的队首进行上述操作。 优点：没有饥饿问题，所有进程都有机会获得 CPU 时间。 缺点：当时间片太小时，产生大量的上下文切换，吞吐量低；当时间片太长时，等待时间过长，不能保证实时性，极限情况退化成 FCFS。 适用场景：适用于分时系统，保证所有进程都能在一定时间内得到执行机会。 ⑤多级反馈队列算法： 原理：先创建多个队列，每个队列都有自己的优先级，第一个队列优先级最高，下来是第二个队列，以此类推。当一个进程需要执行时，先放到第一个队列的末尾，然后从第一个队列的队首开始提取进程分配处理机资源。如果该进程在当前队列规定时间片内无法执行完毕，则移动到下一个队列的队尾。只有当优先级高的队列空闲了，才会去下一个队列的队首提取进程。 优点：结合了多种调度算法的优点，能够根据进程的特性动态调整其优先级。例如，CPU 密集型进程的优先级下降很快，I/O 密集型进程停留在高优先级。 缺点：可能导致饥饿问题，不断有新更高优先级的进程加入。 适用场景：适用于复杂的多任务环境，能够较好地平衡不同类型进程的需求。 3.2实时进程调度算法Linux 实时进程采用 SCHED_FIFO 和 SCHED_RR 调度算法。 ①SCHED_FIFO 特点：实现了一种简单的、先入先出的调度算法，不使用时间片。处于可运行状态的 SCHED_FIFO 级的进程会比任何 SCHED_NORMAL 级的进程都先得到调用。一旦一个 SCHED_FIFO 级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止。只有更高优先级的 SCHED_FIFO 或者 SCHED_RR 任务才能抢占 SCHED_FIFO 任务。如果有两个或者更多的同优先级的 SCHED_FIFO 级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器时才会退出。只要有 SCHED_FIFO 级进程在执行，其他级别较低的进程就只能等待它变为不可运行态后才有机会执行。 实时优先级的静态特性影响：实时优先级只有静态优先级，不会调整优先级，默认优先级为 0 - 99（MAX_RT_PRIO = 100）。这意味着一旦确定了实时进程的优先级，在整个运行过程中它不会因为其他因素而改变，保证了高优先级的实时进程能够在需要时尽快得到执行。 ②SCHED_RR 特点：与 SCHED_FIFO 大体相同，只是 SCHED_RR 级的进程在耗尽事先分配给它的时间后就不能再继续执行了。也就是说，SCHED_RR 是带有时间片的 SCHED_FIFO，是一种实时轮流调度算法。当 SCHED_RR 任务耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度。时间片只用来重新调度同一优先级的进程。对于 SCHED_FIFO 进程，优先级总是立即抢占低优先级，但低优先级进程决不能抢占 SCHED_RR 任务，即使它的时间片耗尽。 实时优先级的静态特性影响：同样，由于实时优先级是静态的，SCHED_RR 进程在确定了优先级后，其执行顺序和时间片的分配都是基于这个固定的优先级。这使得系统在处理实时任务时能够有明确的调度规则，确保关键任务能够在规定的时间内得到执行。 四、Linux进程调度的数据结构与改进4.1Kernel 2.4 的不足Kernel 2.4 的进程调度存在诸多不足。首先，调度算法复杂度是 O (n)，与系统负荷关系较大。例如，2.4 进程调度只设置了一个进程就绪队列，有的进程用完自己时间片后还呆在就绪进程队列里，虽无法取得 CPU 使用权，但仍参与 goodness () 值计算，白白浪费时间。同时，就绪进程队列是全局数据结构，多个 CPU 只有一个就绪队列 runqueue，这使得调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间等待，就绪队列成为明显瓶颈。此外，调度算法在内核态不可抢占，一旦某个进程进入内核态，再高优先级的进程都无法剥夺，只有等该进程返回内核态时才可调度，缺乏对实时进程的支持。 4.2Kernel 2.6 的改进⑴就绪队列改进 Kernel 2.6 对就绪队列进行了重大改进。每个 CPU 有两个按优先级排序的数组：active array 和 expired array。Active array 是当前 CPU 可能选择执行的运行进程队列，队列中的每个进程都有时间片剩下。Expired array 是那些用户时间片用完的就绪进程队列。一旦 active array 里面某个普通进程的时间片用完了，调度器将重新计算进程的时间片、优先级，将它从 active array 中删除，插入到 expired array 中相应优先级队列中。Active array 和 expired array 是通过两个指向每个 CPU 运行队列的指针来访问的。当 active array 中所有的进程都用完时间片，只需将两个指针切换一下就可以了，这比 Kernel 2.4 的切换有了很大改进。例如，在一个拥有多个 CPU 的服务器系统中，这种改进可以显著提高进程调度的效率，减少时间片计算的耗时，从而提高系统的整体性能。 ⑵快速查找进程 Kernel 2.6 引进了一个 64bit 的 bitmap 作为进程队列的索引，用 bitmap 来记载某个优先级的进程队列上有无进程，如果有则为 1。这样使得寻找优先级最高的任务只需要两个 BSFL 命令。在系统中往往有很多的就绪进程，这种设计大大提高了快速找到 CPU 即将运行的进程的效率，成为关系到系统性能的一个重要因素。例如，在一个高负载的系统中，快速查找进程可以确保关键任务能够及时得到执行，提高系统的响应速度。 ⑶负载均衡策略 Kernel 2.6 调度器相关的负载均衡有两种策略，一种是从别的 CPU 上将进程迁移过来，称为 “pull”；一种是将本 CPU 上的进程迁移出去，称为 “push”。这种负载均衡策略可以在多 CPU 系统中有效地平衡各个 CPU 的负载，提高系统的整体性能。例如，当某个 CPU 负载过重而另一个 CPU 负载较轻时，系统可以通过 “pull” 策略从重载 CPU 上 “拉” 进程过来，或者通过 “push” 策略将本 CPU 上的进程迁移出去，从而实现负载的均衡分布。 五、Linux进程调度的特点与应用5.1进程调度器特点Linux 进程调度器对于 CPU 进程调度，采用时间分片的方式，特点如下： 每个进程近似相等的 CPU 使用权：每一个进程有近乎相等的执行时间，对于逻辑 CPU 而言，进程调度使用轮询的方式执行，当轮询完成则回到第一个进程反复。进程数量消耗时间和进程量成正比，虽然这种方式可能导致一些重要任务延迟，但使得系统最为稳定。 进程状态与调度：对于大部分进程来说，不使用时多数处于睡眠状态。除了睡眠状态之外，进程还有运行状态、僵死状态、就绪状态等。当进程处于睡眠状态时，不占用 CPU 时间，只有在某些条件触发时才会获得 CPU 调度分配，如外部存储器访问、用户键入或者鼠标操作触发事件、等待指定时间等。 吞吐量和延迟：吞吐量是处理完成的进程数量与耗费时间的比值。如果进程多过逻辑 CPU 的数量，则再增加进程无法增加吞吐量。延迟是结束处理时间与开始处理时间的差值，多个进程执行会获得近似平均的延迟，进程越多延迟越高。在实际系统中，可能出现空闲进程、进程运行态但未就绪、进程运行态且都就绪等情况，不同情况会对延迟和吞吐量产生不同影响。 5.2多 CPU 调度情况多 CPU 调度主要有两种方式：
多核 CPU 通常只有在同时运行多个进程的时候才会发挥作用，但并不是说有多少核心就有多少倍性能，因为大部分时候进程很少，很多 CPU 都在睡眠状态。如果进程超过逻辑 CPU 数量，无论怎么增加进程都不会提高处理速度。 5.3调度时机与依据⑴调度时机 进程状态转换：进程要调用 sleep () 或 exit () 等函数进行状态转换时，会主动调用调度程序进行进程调度。 当前进程的时间片用完时：由于进程的时间片是由时钟中断来更新的，当当前进程的时间片用完（current->counter = 0），会进行进程切换。 设备驱动程序：当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查 need_resched 的值，如果必要，则调用调度程序 schedule () 主动放弃 CPU。 进程从中断、异常及系统调用返回到用户态时：不管是从中断、异常还是系统调用返回，最终都调用 ret_from_sys_call ()，由这个函数进行调度标志的检测，如果必要，则调用调用调度程序。 ⑵调度依据 Linux 用函数 goodness () 来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了 policy、priority、counter、rt_priority 等四项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值 (weight)，调度程序以这个权值作为选择进程的唯一依据。其中，policy 是进程的调度策略，用来区分实时进程和普通进程；priority 是进程 (包括实时和普通) 的静态优先级；counter 是进程剩余的时间片，它的起始值就是 priority 的值，也可以看作是进程的动态优先级；rt_priority 是实时进程特有的，用于实时进程间的选择。 |
|
|
