调度策略

“调度策略”

为什么会发生调度？

因为cpu是有限的，而操作系统上的进程很多，所以操作系统需要平衡各个进程的运行时间

比如说有的进程运行时间已经很长了，已经占用了cpu很长时间了，这个时候操作系统要公平

就会换下一个需要运行的进程。

抢占 vs 协作从调度机制上来讲，调度可以分为抢占式和协作式。

非抢占, 协作

非抢占方式是指一旦将调度资源 (如 CPU) 分配给某任务后，便让该任务一直执行，直到该任务完成或阻塞或主动让出CPU控制权，非抢占调度又称为协作式调度，它实现简单，并且对共享资源的访问也更安全(如允许使用不可重入函数)。非抢占算法常见的如 FIFO，STCF(Short time to complete first)等。

抢占

抢占方式则允许调度程序根据某种规则，剥夺当前进程的调度资源，将其分配给其它进程。常见的抢占策略有:

基于时间片

基于时间片: 给每个进程分配时间片，当时间片用完后，则停止该进程重新调度下一个进程，这种均分CPU 的算法，又叫轮转调度算法

基于优先级

基于优先级: 给每个进程分配一个优先级，一旦出现一个优先级更高的进程，则停止当前进程并切换到该高优先级进程，这种调度算法又叫优先级抢占轮转调度和优先级抢占结合: 即相同优先级的进程使用轮转调度，如果遇到更高优先级的进程，则可抢占CPU。现代 OS 如 Linux 通常都使用这种混合调度策略。 PS: 基于优先级抢占容易出现优先级反转的问题: 优先级低的任务持有一个被优先级高的任务所需要的共享资源，这种情况下，优先级低的任务有资源而得不到CPU，优先级高的资源有CPU而得不到资源，从而阻塞(导致其它中优先级的任务获得执行)或者忙等(可能永远无法获得资源)。

解决优先级反转的方案:

给临界区一个高优先级，所有进入该临界区的任务将获得该高优先级，避免其被随意抢占当高优先级任务在等待低优先级进程持有资源时，低优先级进程将暂时获得高优先级进程的优先级，VxWorks采用的方式。禁止中断，也就是在临界区不可被抢占，Linux 采用的就是这种方式，在 thread_info.preeempt_count 记录每个进程当前持锁计数。另外，调度器是不能在进程指令流的任意一点执行打断的，因为进程可能此时正在做任何事情，如系统调用，死循环，锁操作等，要实现任意状态的可抢占性代价是很大的，需要 OS 和 App 的通力配合，特别是在涉及在内核态的时候，目前所有OS都不能在进程执行的任意点进行抢占。只是说不断让抢占区更大，抢占点尽可能地密集。

实时 vs 非实时从系统需求或用户角度而言，调度系统可以分为实习系统和非实时系统。

在实时操作系统中，系统必须在特定的时间内完成指定的应用。实时通常分为软实时(soft real-time)和硬实时(hard real-time)，硬实时是指系统要有确定的最坏情况下的服务时间，即对于事件的响应时间截止期限无论如何都必须得到满足，通常应用在军工航天领域。而软实时只提供统计意义上的实时，比如应用要求在95%的情况下都会确保在规定的时间内执行某个任务，而不一定要求100%。实时系统通常采用抢占调度，实现一个硬实时系统的代价是很高的，要做到进程可以在任意时刻被抢占，在现代OS上来讲，基本是不可能的，因为OS的很多系统调用都是不可被打断的，并且很多操作具备时间的随机性，比如 CPU Cache Miss，Page Fault，CPU Branch Predictor 等等。

BTW, 为什么现代OS不尽可能地去掉这些不稳定性(如虚拟内存，CPU多级Cache，分支预测等)，从而为成为实时系统打好基础呢？对桌面操作系统而言，对实时性的要求没有那么高，应用切换偶尔卡一卡并无大碍，桌面系统更关注的一方面是对内核的统一抽象，屏蔽硬件差异化，接口丰富易用，让上层应用易于开发，比如虚拟内存，文件描述符等。另一方面，桌面系统在选择牺牲部分的实时性来提高吞吐量，比如多级Cache，分支预测。因此尽管如 Linux 这类桌面系统支持实时优先级和多种调度机制，但仍然最多只能实现软实时，这是设计目标决定的。

而非实时系统，则没有对最低任务处理时延的要求，比如简单的非抢占调度模型。

调度结构这里我们讨论基于OS之上的几种常见的应用层调度。对应用层而言，所谓调度器(scheduler)便是OS线程，在此之上应用实现自己的任务，任务队列，以及调度算法。

single scheduler

这是最简单的模型，实际上，几乎所有调度器最开始就是这样的，如Go,Erlang,甚至OS(单核年代)的早期版本，复杂项目的通用最佳实践是先跑起来再优化(“First make it work, then measure, then optimize”.)。这种调度模型只有一个调度器和一个任务队列，由于不需要锁，所以单核吞吐量很高，主要的缺点在于无法充分利用调度资源(如多核)，并且容易出现任务饥饿(多调度器本质也会有这种情况，只不过被掩盖了一些)。

multi scheduler with global queue 为了最大化多核收益，我们需要多个调度器，理想情况下是调度器的数量和CPU核心数一致。因此有了如下调度模型:

如图，多个调度器共享一个全局任务队列，Erlang OTP R11B 便使用这种模型，该模型主要的瓶颈在于全局任务队列的操作需要加锁，并且CPU核心数越多，调度瓶颈越明显，从而限制了调度算法在多核下的扩展性。

multi scheduler with local queue 为了优化全局任务队列带来的瓶颈问题，借鉴"Cache思维”，可以给每个调度器分配一个本地的任务队列:

这样调度器可以无锁操作本地任务队列，显著减少锁竞争，提升多核下的调度效率。但这样又引入了新的问题: 如何尽可能地让各个调度器都随时有事情做(任务分配尽可能均衡)。比如如果给每个调度器本地任务队列分配了10个任务，执行最快的调度器A执行完这10个任务时，执行最慢的调度器B可能才执行完第一个，在这种情况下，调度器A是否应该去调度B的任务队列steal(窃取)一部分任务过来，以让整体调度效率最高。这个过程叫任务迁移(Task Migration)或任务窃取(Task Stealing)。Erlang R13B+ 和 Go 调度都是基于此结构，但有一些区别。

以上三种模型是大多数调度器历经的三个阶段，最终演化得到的是一个多层次，局部性的结构(类似 CPU Cache层级)。

现实中的调度器就调度器结构而言，各个调度算法大同小异，各个调度算法的根本差异还是在调度策略上，基于设计目标，在复杂性，吞吐量，实时性之间去做取舍，这里我仍然想以 Erlang 和 Go来举例说明。

基于Erlang的产生背景(通信领域)，Erlang 在设计之初就对实时性(低延迟)非常看重，为了达成软实时性，Erlang的调度必然是抢占式的，它通过给每个Erlang进程设定规约(Reduction)来作为一个进程的虚拟时间片，进程调用函数，BIF，GC，ETS操作，发送消息等，都会消耗规约，甚至用Erlang自带的用C写的正则表达式处理，也添加了扣除规约的代码，每个Erlang进程默认有2000规约，在Erlang的设计理念中，天下没有"免费"的操作，它重度依靠规约来衡量进程何时被换出。但理想和现实往往有差别，NIF的出现打破了这个定律，NIF是用户用C实现的可供Erlang调用的函数，它是不可被调度的，对此，Erlang打出了如下补丁:

官方建议NIF不要超过1ms(相信开发者对自己写的代码心里有数…) 在NIF中给Erlang虚拟机手动汇报当前执行时间，并手动记录上下文和恢复(抢占式变成了协作式，强制变成了自愿…) 将NIF放到自己创建的OS线程中执行，通过消息的方式将结果返回到Erlang进程(走开，别脏了我的公平调度器) 将NIF放到OTP为你准备的脏调度器(OTP R17引入，需要在启动时通过参数开启)中执行(好吧，我给你提供脏调度器) PS: Erlang OTP R17之后提供了脏调度器功能，这也是继R13B之后对调度结构的又一次改进，虚拟机调度器就变成了M+N个。

以上方案可以说都是治标不治本，所以写纯Erlang代码，你可以享受到它很多的便利，但是一旦你因为性能问题，或要对接外部库等各种原因需要用到C的时候，一切都开始不美好了。

Erlang 的另一个问题也来自于其"公平调度”，我们假设有10000个逻辑进程，它们会将日志数据发到一个logger进程，那么系统上一共有10001个进程(忽略其它)，理想情况下，我们当然希望这个logger有任务就处理，避免消息堆积，最大化吞吐量，但Erlang的公平调度会想尽办法让这个logger进程和其它逻辑进程平起平坐，哪怕它有很多事情要做，然后导致导致logger进程消息队列膨胀，内存随之增长，甚至VM随之挂掉。针对这个问题通常的处理方案是:

提升logger进程的优先级(没有具体测试过) 开多个logger进程争取更多的执行权(笨办法) 从设计上尽量避免这种扇入扇出模型，同一节点尽可能跑相同类型的任务，比如将logger放到其它节点(Erlang的"并发思维”) 通过NIF来绕过时间片限制(骚操作) 因此，我们通常说Erlang在进程数少的时候表现不怎么样，而在进程多的却有很好的低延时表现。Erlang 调度器还有一些其它细节没有提到，比如:

通过三个优先级队列(low/normal,high,max)来实现进程的优先级调度当调度器idle时，会自旋一段时间，如果没有新任务到达，则关闭该调度器(节能减排) 除了Process外，Erlang还处理Port任务，Port是Erlang与外部通信(文件，网络，C等)的一种机制 Erlang对网络IO进行了特别的优化(System Level Activities)，即将所有的 socket 设置为非阻塞，然后通过epoll机制去轮询并唤醒调用进程，通过应用层的阻塞/唤醒模拟系统调用。反过来谈 Go，如果说 Erlang 为实时性殚精竭虑的话，那么Go则要实务得多，更加偏向于吞吐量和实用性，我之前谈过Go GPM模型，Go没有时间片或规约的概念，它的抢占也不是完全抢占的，它通过一个后台线程sysmon来监控并决定何时发起抢占，何时 GC 等，比如一个goroutine执行超过了10ms，sysmon则会向其发出抢占请求。抢占的方式也很简单，给goroutine打一个标记，goroutine在调用函数分配函数栈时会检查该标记，来决定当前G是否应该让出调度权，因此它没办法抢占死循环。可以看到，Go的调度模型实现相对比较简单，一方面可能调度器仍然还很年轻(STW的痛还历历在目)，另一方面Go的设计哲学就是简单。如果要解释得再官方一些: Go 更看重吞吐量，而非实时性。

另外，由于Erlang和Go都是为服务器设计的语言，因此它们都是网络IO进行了优化，将所有 socket 设置为 nonblock，通过轮询/唤醒来向应用层屏蔽系统调用，通过IO复用+应用层阻塞来避免调度器阻塞在系统调用上。

最后要理解一个调度器，需要结合其产生背景，设计目标，变更历史等，万丈高楼平地起，调度器这类复杂的系统，通常都是"First make it work, then measure, then optimize”，比如 Erlang 的 NIF，Go 的 STW 等，都在逐渐优化。

实时性和吞吐量是不可兼得的，这已经在其它系统上得到了验证。实时系统通常实现都比较复杂，并且由于现代 OS 最多满足软实时特性，因此应用层的调度也最多实现软实时。严格意义上的硬实时系统通常由特定领域的嵌入式系统实现。同时，也因为应用层的调度受更底层的OS调度的影响，要达到一个系统的整体最优，需要协调不同的调度层级，比如 Erlang 提供一个+sbt参数可以将调度器与 CPU 核心绑定，这样可以更好地利用 CPU 缓存和局部性，以提升整体性能。

Linux 进程的睡眠和唤醒

在Linux中，仅等待 CPU 时间的进程称为就绪进程，它们被放置在一个运行队列中，一个就绪进程的状态标志位为 TASK_RUNNING。一旦一个运行中的进程时间片用完， Linux 内核的调度器会剥夺这个进程对 CPU 的控制权，并且从运行队列中选择一个合适的进程投入运行。

当然，一个进程也可以主动释放 CPU 的控制权。函数 schedule() 是一个调度函数，它可以被一个进程主动调用，从而调度其它进程占用 CPU。一旦这个主动放弃 CPU 的进程被重新调度占用 CPU，那么它将从上次停止执行的位置开始执行，也就是说它将从调用 schedule() 的下一行代码处开始执行。

有时候，进程需要等待直到某个特定的事件发生，例如设备初始化完成、I/O 操作完成或定时器到时等。在这种情况下，进程则必须从运行队列移出，加入到一个等待队列中，这个时候进程就进入了睡眠状态。

Linux 中的进程睡眠状态有两种: 一种是可中断的睡眠状态，其状态标志位

TASK_INTERRUPTIBLE；

另一种是不可中断的睡眠状态，其状态标志位为 TASK_UNINTERRUPTIBLE。可中断的睡眠状态的进程会睡眠直到某个条件变为真，比如说产生一个硬件中断、释放进程正在等待的系统资源或是传递一个信号都可以是唤醒进程的条件。不可中断睡眠状态与可中断睡眠状态类似，但是它有一个例外，那就是把信号传递到这种睡眠状态的进程不能改变它的状态，也就是说它不响应信号的唤醒。不可中断睡眠状态一般较少用到，但在一些特定情况下这种状态还是很有用的，比如说: 进程必须等待，不能被中断，直到某个特定的事件发生。

在现代的 Linux 操作系统中，进程一般都是用调用 schedule() 的方法进入睡眠状态的，下面的代码演示了如何让正在运行的进程进入睡眠状态。

sleeping_task = current; set_current_state(TASK_INTERRUPTIBLE); schedule(); func1(); /Rest of the code …/

在第一个语句中，程序存储了一份进程结构指针 sleeping_task，current 是一个宏，它指向正在执行的进程结构。set_current_state() 将该进程的状态从执行状态 TASK_RUNNING 变成睡眠状态TASK_INTERRUPTIBLE。如果 schedule() 是被一个状态为TASK_RUNNING 的进程调度，那么 schedule() 将调度另外一个进程占用 CPU；如果 schedule() 是被一个状态为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 的进程调度，那么还有一个附加的步骤将被执行: 当前执行的进程在另外一个进程被调度之前会被从运行队列中移出，这将导致正在运行的那个进程进入睡眠，因为它已经不在运行队列中了。

我们可以使用下面的这个函数将刚才那个进入睡眠的进程唤醒。

wake_up_process(sleeping_task);

在调用了 wake_up_process() 以后，这个睡眠进程的状态会被设置为 TASK_RUNNING，而且调度器会把它加入到运行队列中去。当然，这个进程只有在下次被调度器调度到的时候才能真正地投入运行。

2 无效唤醒

几乎在所有的情况下，进程都会在检查了某些条件之后，发现条件不满足才进入睡眠。可是有的时候进程却会在判定条件为真后开始睡眠，如果这样的话进程就会无限期地休眠下去，这就是所谓的无效唤醒问题。在操作系统中，当多个进程都企图对共享数据进行某种处理，而最后的结果又取决于进程运行的顺序时，就会发生竞争条件，这是操作系统中一个典型的问题，无效唤醒恰恰就是由于竞争条件导致的。

设想有两个进程 A 和 B，A 进程正在处理一个链表，它需要检查这个链表是否为空，如果不空就对链表里面的数据进行一些操作，同时 B 进程也在往这个链表添加节点。当这个链表是空的时候，由于无数据可操作，这时 A 进程就进入睡眠，当 B 进程向链表里面添加了节点之后它就唤醒 A 进程，其代码如下:

A 进程:

1 spin_lock(&list_lock); 2if(list_empty(&list_head)) { 3 spin_unlock(&list_lock); 4 set_current_state(TASK_INTERRUPTIBLE); 5 schedule(); 6 spin_lock(&list_lock); 7 } 8 9/Rest of the code …/ 10 spin_unlock(&list_lock);

B 进程:

100 spin_lock(&list_lock); 101 list_add_tail(&list_head, new_node); 102 spin_unlock(&list_lock); 103 wake_up_process(processa_task);

这里会出现一个问题，假如当 A 进程执行到第 3 行后第 4 行前的时候，B 进程被另外一个处理器调度投入运行。在这个时间片内，B 进程执行完了它所有的指令，因此它试图唤醒 A 进程，而此时的 A 进程还没有进入睡眠，所以唤醒操作无效。在这之后，A 进程继续执行，它会错误地认为这个时候链表仍然是空的，于是将自己的状态设置为 TASK_INTERRUPTIBLE 然后调用 schedule() 进入睡眠。由于错过了 B 进程唤醒，它将会无限期的睡眠下去，这就是无效唤醒问题，因为即使链表中有数据需要处理，A 进程也还是睡眠了。

3 避免无效唤醒

如何避免无效唤醒问题呢？我们发现无效唤醒主要发生在检查条件之后和进程状态被设置为睡眠状态之前，本来 B 进程的 wake_up_process() 提供了一次将 A 进程状态置为 TASK_RUNNING 的机会，可惜这个时候 A 进程的状态仍然是 TASK_RUNNING，所以 wake_up_process() 将 A 进程状态从睡眠状态转变为运行状态的努力没有起到预期的作用。要解决这个问题，必须使用一种保障机制使得判断链表为空和设置进程状态为睡眠状态成为一个不可分割的步骤才行，也就是必须消除竞争条件产生的根源，这样在这之后出现的 wake_up_process () 就可以起到唤醒状态是睡眠状态的进程的作用了。找到了原因后，重新设计一下 A 进程的代码结构，就可以避免上面例子中的无效唤醒问题了。

A 进程:

1 set_current_state(TASK_INTERRUPTIBLE); 2 spin_lock(&list_lock); 3if(list_empty(&list_head)) { 4 spin_unlock(&list_lock); 5 schedule(); 6 spin_lock(&list_lock); 7 } 8 set_current_state(TASK_RUNNING); 9 10/Rest of the code …/ 11 spin_unlock(&list_lock);

可以看到，这段代码在测试条件之前就将当前执行进程状态转设置成 TASK_INTERRUPTIBLE 了，并且在链表不为空的情况下又将自己置为 TASK_RUNNING 状态。这样一来如果 B 进程在 A 进程进程检查了链表为空以后调用 wake_up_process()，那么 A 进程的状态就会自动由原来 TASK_INTERRUPTIBLE变成 TASK_RUNNING，此后即使进程又调用了 schedule()，由于它现在的状态是 TASK_RUNNING，所以仍然不会被从运行队列中移出，因而不会错误的进入睡眠，当然也就避免了无效唤醒问题。

4 Linux 内核的例子

在 Linux 操作系统中，内核的稳定性至关重要，为了避免在 Linux 操作系统内核中出现无效唤醒问题， Linux 内核在需要进程睡眠的时候应该使用类似如下的操作:

/‘q’是我们希望睡眠的等待队列/ DECLARE_WAITQUEUE(wait,current); add_wait_queue(q, &wait); set_current_state(TASK_INTERRUPTIBLE); /或 TASK_INTERRUPTIBLE/ while(!condition) /‘condition’ 是等待的条件/ schedule(); set_current_state(TASK_RUNNING); remove_wait_queue(q, &wait);

上面的操作，使得进程通过下面的一系列步骤安全地将自己加入到一个等待队列中进行睡眠: 首先调用 DECLARE_WAITQUEUE () 创建一个等待队列的项，然后调用 add_wait_queue() 把自己加入到等待队列中，并且将进程的状态设置为TASK_INTERRUPTIBLE 或者 TASK_INTERRUPTIBLE。然后循环检查条件是否为真: 如果是的话就没有必要睡眠，如果条件不为真，就调用 schedule()。当进程检查的条件满足后，进程又将自己设置为 TASK_RUNNING 并调用 remove_wait_queue() 将自己移出等待队列。

从上面可以看到，Linux 的内核代码维护者也是在进程检查条件之前就设置进程的状态为睡眠状态，然后才循环检查条件。如果在进程开始睡眠之前条件就已经达成了，那么循环会退出并用 set_current_state() 将自己的状态设置为就绪，这样同样保证了进程不会存在错误的进入睡眠的倾向，当然也就不会导致出现无效唤醒问题。

下面让我们用 linux 内核中的实例来看看 Linux 内核是如何避免无效睡眠的，这段代码出自 Linux2.6 的内核 (linux-2.6.11/kernel/sched.c: 4254):

4253/Wait for kthread_stop/ 4254 set_current_state(TASK_INTERRUPTIBLE); 4255while (!kthread_should_stop()) { 4256 schedule(); 4257 set_current_state(TASK_INTERRUPTIBLE); 4258 } 4259 __set_current_state(TASK_RUNNING); 4260return0;

上面的这些代码属于迁移服务线程 migration_thread，这个线程不断地检查 kthread_should_stop()，

直到 kthread_should_stop() 返回 1 它才可以退出循环，也就是说只要 kthread_should_stop() 返回 0 该进程就会一直睡眠。从代码中我们可以看出，检查 kthread_should_stop() 确实是在进程的状态被置为 TASK_INTERRUPTIBLE 后才开始执行的。因此，如果在条件检查之后但是在 schedule() 之前有其他进程试图唤醒它，那么该进程的唤醒操作不会失效。

小结

通过上面的讨论，可以发现在 Linux 中避免进程的无效唤醒的关键是在进程检查条件之前就将进程的状态置为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，并且如果检查的条件满足的话就应该将其状态重新设置为 TASK_RUNNING。这样无论进程等待的条件是否满足，进程都不会因为被移出就绪队列而错误地进入睡眠状态，从而避免了无效唤醒问题。

作者: chumojing

原文地址: http://blog.chinaunix.net/uid-12461657-id-3178775.html专业Linux

https://zhuanlan.zhihu.com/p/56818057

Contents