概述

操作系统要实现多进程。进程调度不可缺少。

有人说，进程调度是操作系统中最为重要的一个部分。我认为这样的说法说得太绝对了一点，就像非常多人动辄就说“某某函数比某某函数效率高XX倍”一样。脱离了实际环境。这些结论是比較片面的。 

而进程调度到底有多重要呢？ 首先，我们须要明白一点：进程调度是对 TASK_RUNNING 状态的进程进行调度。假设进程不可运行（正在睡眠或其它），那么它跟进程调度没多大关系。

所以，假设你的系统负载很低，盼星星盼月亮才出现一个可运行状态的进程。那么进程调度也就不会太重要。

哪个进程可运行，就让它运行去，没有什么须要多考虑的。反之，假设系统负载很高，时时刻刻都有 N 多个进程处于可运行状态，等待被调度运行。那么进程调度程序为了协调这 N 个进程的运行，必然得做非常多工作。

协调得不好，系统的性能就会大打折扣。

这个时候，进程调度就是非常重要的。

虽然我们寻常接触的非常多计算机（如桌面系统、网络server、等）负载都比較低，可是 linux 作为一个通用操作系统。不能如果系统负载低，必须为应付高负载下的进程调度做精心的设计。

当然。这些设计对于低负载（且没有什么实时性要求）的环境，没多大用。极端情况下，如果 CPU 的负载始终保持 0 或 1（永远都仅仅有一个进程或没有进程须要在 CPU 上执行）。那么这些设计基本上都是徒劳的。

优先级

如今的操作系统为了协调多个进程的“同一时候”运行，最主要的手段就是给进程定义优先级。

定义了进程的优先级，假设有多个进程同一时候处于可运行状态。那么谁优先级高谁就去运行，没有什么好纠结的了。

那么，进程的优先级该怎样确定呢？有两种方式：由用户程序指定、由内核的调度程序动态调整。（以下会说到）

linux 内核将进程分成两个级别：普通进程和实时进程。实时进程的优先级都高于普通进程，除此之外。它们的调度策略也有所不同。

实时进程的调度

实时。原本的涵义是“给定的操作一定要在确定的时间内完毕”。重点并不在于操作一定要处理得多快，而是时间要可控（在最坏情况下也不能突破给定的时间）。

这种“实时”称为“硬实时”，多用于非常精密的系统之中（比方什么火箭、导弹之类的）。一般来说，硬实时的系统是相对照较专用的。

像 linux 这种通用操作系统显然没法满足这种要求，中断处理、虚拟内存、等机制的存在给处理时间带来了非常大的不确定性。

硬件的 cache、磁盘寻道、总线争用、也会带来不确定性。

比方考虑“i++;”这么一句 C 代码。绝大多数情况下。它运行得非常快。

可是极端情况下还是有这种可能：

1、i 的内存空间未分配。CPU 触发缺页异常。

而 linux 在缺页异常的处理代码中试图分配内存时，又可能因为系统内存紧缺而分配失败，导致进程进入睡眠；

2、代码运行过程中硬件产生中断。linux 进入中断处理程序而搁置当前进程。

而中断处理程序的处理过程中又可能发生新的硬件中断，中断永远嵌套不止……；

等等……

而像 linux 这样号称实现了“实时”的通用操作系统，事实上仅仅是实现了“软实时”。即尽可能地满足进程的实时需求。

假设一个进程有实时需求（它是一个实时进程），则仅仅要它是可运行状态的，内核就一直让它运行。以尽可能地满足它对 CPU 的须要，直到它完毕所须要做的事情，然后睡眠或退出（变为非可运行状态）。

而假设有多个实时进程都处于可运行状态。则内核会先满足优先级最高的实时进程对 CPU 的须要，直到它变为非可运行状态。

于是。仅仅要高优先级的实时进程一直处于可运行状态。低优先级的实时进程就一直不能得到 CPU。仅仅要一直有实时进程处于可运行状态，普通进程就一直不能得到 CPU。

（后来，内核加入了 /proc/sys/kernel/sched_rt_runtime_us和 /proc/sys/kernel/sched_rt_period_us 两个參数，限定了在以 sched_rt_period_us 为周期的时间内，实时进程最多仅仅能运行 sched_rt_runtime_us 这么多时间。这样就在一直有实时进程处于可运行状态的情况下。给普通进程留了一点点可以得到运行的机会。

那么，假设多个同样优先级的实时进程都处于可运行状态呢？这时就有两种调度策略可供选择：

1、SCHED_FIFO：先进先出。

直到先被运行的进程变为非可运行状态。后来的进程才被调度运行。在这样的策略下，先来的进程能够运行 sched_yield 系统调用。自愿放弃CPU。以让权给后来的进程；

2、SCHED_RR：轮转调度。

内核为实时进程分配时间片，在时间片用完时。让下一个进程使用 CPU。

强调一下，这两种调度策略只针对于同样优先级的多个实时进程同一时候处于可运行状态的情况。

在 linux 下。用户程序能够通过 sched_setscheduler 系统调用来设置进程的调度策略以及相关调度參数；sched_setparam 系统调用则仅仅用于设置调度參数。这两个系统调用要求用户进程具有设置进程优先级的能力（CAP_SYS_NICE，一般来说须要 root 权限）。

通过将进程的策略设为 SCHED_FIFO 或 SCHED_RR，使得进程变为实时进程。而进程的优先级则是通过以上两个系统调用在设置调度參数时指定的。

对于实时进程，内核不会试图调整其优先级。由于进程实时与否？有多实时？这些问题都是跟用户程序的应用场景相关。仅仅实用户可以回答，内核不能臆断。

综上所述。实时进程的调度是很easy的。进程的优先级和调度策略都由用户定死了，内核仅仅须要总是选择优先级最高的实时进程来调度运行就可以。唯一略微麻烦一点的仅仅是在选择具有同样优先级的实时进程时，要考虑两种调度策略。

普通进程的调度

实时进程调度的中心思想是，让处于可运行状态的最高优先级的实时进程尽可能地占有 CPU。由于它有实时需求；而普通进程则被觉得是没有实时需求的进程，于是调度程序力图让各个处于可运行状态的普通进程和平共处地分享 CPU。从而让用户觉得这些进程是同一时候运行的。

与实时进程相比，普通进程的调度要复杂得多。内核须要考虑两件麻烦事：

一、动态调整进程的优先级
按进程的行为特征。能够将进程分为“交互式进程”和“批处理进程”：
交互式进程（如桌面程序、server、等）基本的任务是与外界交互。这种进程应该具有较高的优先级，它们总是睡眠等待外界的输入。而在输入到来，内核将其唤醒时。它们又应该非常快被调度运行，以做出响应。比方一个桌面程序，假设鼠标点击后半秒种还没反应。用户就会感觉系统“卡”了；

批处理进程（如编译程序）基本的任务是做持续的运算，因而它们会持续处于可执行状态。这种进程一般不须要高优先级，比方编译程序多执行了几秒种，用户多半不会太在意；

假设用户可以明白知道进程应该有如何的优先级，可以通过 nice、setpriority 系统调用来对优先级进行设置。

（假设要提高进程的优先级。要求用户进程具有 CAP_SYS_NICE 能力。）

然而应用程序未必就像桌面程序、编译程序这样典型。程序的行为可能五花八门，可能一会儿像交互式进程，一会儿又像批处理进程。以致于用户难以给它设置一个合适的优先级。再者，即使用户明白知道一个进程是交互式还是批处理，也多半碍于权限或由于偷懒而不去设置进程的优先级。（你又是否为某个程序设置过优先级呢？）于是，终于，区分交互式进程和批处理进程的重任就落到了内核的调度程序上。

调度程序关注进程近一段时间内的表现（主要是检查其睡眠时间和执行时间）。依据一些经验性的公式。推断它如今是交互式的还是批处理的？程度怎样？最后决定给它的优先级做一定的调整。

进程的优先级被动态调整后。就出现了两个优先级：
1、用户程序设置的优先级（假设未设置，则使用默认值），称为静态优先级。

这是进程优先级的基准，在进程运行的过程中往往是不改变的。
2、优先级动态调整后。实际生效的优先级。这个值是可能时时刻刻都在变化的。

二、调度的公平性
在支持多进程的系统中，理想情况下，各个进程应该是依据其优先级公平地占有 CPU。

而不会出现“谁运气好谁占得多”这种不可控的情况。

linux实现公平调度基本上是两种思路：

1、给处于可运行状态的进程分配时间片（依照优先级），用完时间片的进程被放到“过期队列”中。等可运行状态的进程都过期了。再又一次分配时间片；

2、动态调整进程的优先级。

随着进程在CPU上执行，其优先级被不断调低。以便其它优先级较低的进程得到执行机会。

后一种方式有更小的调度粒度，而且将“公平性”与“动态调整优先级”两件事情合而为一，大大简化了内核调度程序的代码。因此，这样的方式也成为内核调度程序的新宠。

强调一下，以上两点都是仅针对普通进程的。而对于实时进程，内核既不能自作多情地去动态调整优先级，也没有什么公平性可言。

普通进程详细的调度算法很复杂，而且随 linux 内核版本号的演变也在不断更替（不不过简单的调整），所以本文就不继续深入了。有兴趣的朋友能够參考以下的链接：

《Linux 调度器发展简述》

《鼠眼看Linux调度器》

《鼠眼再看Linux调度器［1］》

《鼠眼再看Linux调度器［2］》

调度程序的效率

“优先级”明白了哪个进程应该被调度运行。而调度程序还必需要关心效率问题。调度程序跟内核中的非常多过程一样会频繁被运行，假设效率不济就会浪费非常多CPU时间，导致系统性能下降。

在linux 2.4时，可执行状态的进程被挂在一个链表中。

每次调度。调度程序须要扫描整个链表。以找出最优的那个进程来执行。复杂度为O(n)。

在linux 2.6早期，可运行状态的进程被挂在N(N=140)个链表中。每个链表代表一个优先级，系统中支持多少个优先级就有多少个链表。

每次调度，调度程序仅仅须要从第一个不为空的链表中取出位于链表头的进程就可以。这样就大大提高了调度程序的效率，复杂度为O(1)；

在linux 2.6最近的版本号中，可运行状态的进程依照优先级顺序被挂在一个红黑树（能够想象成平衡二叉树）中。每次调度，调度程序须要从树中找出优先级最高的进程。

复杂度为O(logN)。

那么，为什么从linux 2.6早期到最近linux 2.6版本号，调度程序选择进程时的复杂度反而添加了呢？

这是由于，与此同一时候，调度程序对公平性的实现从上面提到的第一种思路改变为另外一种思路（通过动态调整优先级实现）。

而O(1)的算法是基于一组数目不大的链表来实现的。按我的理解，这使得优先级的取值范围非常小（区分度非常低）。不能满足公平性的需求。

而使用红黑树则对优先级的取值没有限制（能够用32位、 64位、或很多其它位来表示优先级的值），而且O(logN)的复杂度也还是非常高效的。

调度触发的时机

调度的触发主要有例如以下几种情况：
1、当前进程（正在CPU上执行的进程）状态变为非可执行状态。

进程运行系统调用主动变为非可运行状态。比方运行nanosleep进入睡眠、运行exit退出、等等；

进程请求的资源得不到满足而被迫进入睡眠状态。比方运行read系统调用时，磁盘快速缓存里没有所须要的数据，从而睡眠等待磁盘IO；

进程响应信号而变为非可运行状态。比方响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等；

2、抢占。

进程执行时，非预期地被剥夺CPU的使用权。这又分两种情况：进程用完了时间片、或出现了优先级更高的进程。

优先级更高的进程受正在CPU上执行的进程的影响而被唤醒。

如发送信号主动唤醒，或由于释放相互排斥对象（如释放锁）而被唤醒；

内核在响应时钟中断的过程中。发现当前进程的时间片用完；

内核在响应中断的过程中，发现优先级更高的进程所等待的外部资源的变为可用，从而将其唤醒。

比方CPU收到网卡中断，内核处理该中断，发现某个 socket可读。于是唤醒正在等待读这个socket的进程。再比方内核在处理时钟中断的过程中，触发了定时器。从而唤醒相应的正在nanosleep 系统调用中睡眠的进程；

其它问题

1、内核抢占

理想情况下。仅仅要满足“出现了优先级更高的进程”这个条件，当前进程就应该被立马抢占。可是，就像多线程程序须要用锁来保护临界区资源一样，内核中也存在非常多这种临界区。不大可能随时随地都能接收抢占。

linux 2.4时的设计就很easy，内核不支持抢占。

进程执行在内核态时（比方正在执行系统调用、正处于异常处理函数中），是不同意抢占的。必须等到返回用户态时才会触发调度（确切的说，是在返回用户态之前，内核会专门检查一下是否须要调度）；
linux 2.6则实现了内核抢占，可是在非常多地方还是为了保护临界区资源而须要暂时性的禁用内核抢占。

也有一些地方是出于效率考虑而禁用抢占，比較典型的是spin_lock。spin_lock是这样一种锁，假设请求加锁得不到满足（锁已被别的进程占有），则当前进程在一个死循环中不断检測锁的状态，直到锁被释放。

为什么要这样忙等待呢？由于临界区非常小，比方仅仅保护“i+=j++;”这么一句。假设由于加锁失败而形成“睡眠-唤醒”这么个过程，就有些得不偿失了。

那么既然当前进程忙等待（不睡眠），谁又来释放锁呢？事实上已得到锁的进程是执行在还有一个CPU上的，而且是禁用了内核抢占的。这个进程不会被其它进程抢占。所以等待锁的进程仅仅有可能执行在别的CPU上。（假设仅仅有一个CPU呢？那么就不可能存在等待锁的进程了。）

而假设不禁用内核抢占呢？那么得到锁的进程将可能被抢占。于是可能非常久都不会释放锁。于是，等待锁的进程可能就不知何年何月得偿所望了。

对于一些实时性要求更高的系统，则不能容忍spin_lock这种东西。宁可改用更费劲的“睡眠-唤醒”过程。也不能由于禁用抢占而让更高优先级的进程等待。比方，嵌入式实时linux montavista就是这么干的。

由此可见，实时并不代表高效。非常多时候为了实现“实时”，还是须要对性能做一定让步的。

2、多处理器下的负载均衡
前面我们并没有专门讨论多处理器对调度程序的影响。事实上也没有什么特别的，就是在同一时刻能有多个进程并行地执行而已。

那么。为什么会有“多处理器负载均衡”这个事情呢？

假设系统中仅仅有一个可运行队列，哪个CPU空暇了就去队列中找一个最合适的进程来运行。

这样不是非常好非常均衡吗？

的确如此，可是多处理器共用一个可运行队列会有一些问题。显然，每一个CPU在运行调度程序时都须要把队列锁起来，这会使得调度程序难以并行，可能导致系统性能下降。而假设每一个CPU相应一个可运行队列则不存在这种问题。

另外，多个可运行队列另一个优点。这使得一个进程在一段时间内总是在同一个CPU上运行，那么非常可能这个CPU的各级cache中都缓存着这个进程的数据，非常有利于系统性能的提升。

所以，在linux下，每一个CPU都有着相应的可运行队列，而一个可运行状态的进程在同一时刻仅仅能处于一个可运行队列中。

于是，“多处理器负载均衡”这个麻烦事情就来了。内核须要关注各个CPU可运行队列中的进程数目，在数目不均衡时做出适当调整。什么时候须要调整，以多大力度进程调整，这些都是内核须要关心的。当然，尽量不要调整最好。毕竟调整起来又要耗CPU、又要锁可运行队列，代价还是不小的。

另外，内核还得关心各个CPU的关系。两个CPU之间，可能是相互独立的、可能是共享cache的、甚至可能是由同一个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要根据。关系越紧密。就应该越能容忍“不均衡”。

更细节的东西能够參考一下关于“调度域”的文章。

3、优先级继承
由于相互排斥，一个进程（设为A）可能由于等待进入临界区而睡眠。直到正在占有对应资源的进程（设为B）退出临界区，进程A才被唤醒。

可能存在这种情况：A的优先级很高。B的优先级很低。B进入了临界区，可是却被其它优先级较高的进程（设为C）抢占了，而得不到执行，也就无法退出临界区。于是A也就无法被唤醒。

A有着非常高的优先级，可是如今却沦落到跟B一起，被优先级并不太高的C抢占，导致运行被推迟。

这样的现象就叫做优先级反转。

出现这样的现象是非常不合理的。

较好的应对措施是：当A開始等待B退出临界区时。B暂时得到A的优先级（还是如果A的优先级高于B），以便顺利完毕处理过程，退出临界区。之后B的优先级恢复。这就是优先级继承的方法。

为了实现优先级继承，内核又得做非常多事情。更细节的东西能够參考一下关于“优先级反转”或“优先级继承”的文章。

4、中断处理线程化
在linux下。中断处理程序执行于一个不可调度的上下文中。

从CPU响应硬件中断自己主动跳转到内核设定的中断处理程序去执行，到中断处理程序退出。整个过程是不能被抢占的。

一个进程假设被抢占了，能够通过保存在它的进程控制块（task_struct）中的信息，在之后的某个时间恢复它的执行。而中断上下文则没有task_struct。被抢占了就没法恢复了。

中断处理程序不能被抢占，也就意味着中断处理程序的“优先级”比不论什么进程都高（必须等中断处理程序完毕了。进程才干被运行）。

可是在实际的应用场景中，可能某些实时进程应该得到比中断处理程序更高的优先级。

于是，一些实时性要求更高的系统就给中断处理程序赋予了task_struct以及优先级，使得它们在必要的时候可以被高优先级的进程抢占。可是显然，做这些工作是会给系统造成一定开销的，这也是为了实现“实时”而对性能做出的一种让步

很多其它细节能够參考一下关于“中断线程化”的文章。

转自：http://blog.csdn.net/tennysonsky/article/details/44964597

转自：linux 进程调度浅析