操作系统要实现多进程，进程调度必不可少。有人说，进程调度是操作系统中最为重要的1个部份。我觉得这类说法说得太绝对了1点，就像很多人动辄就说“某某函数比某某函数效力高XX倍”1样，脱离了实际环境，这些结论是比较片面的。
而进程调度究竟有多重要呢？ 首先，我们需要明确1点：进程调度是对 TASK_RUNNING 状态的进程进行调度。如果进程不可履行（正在睡眠或其他），那末它跟进程调度没多大关系。所以，如果你的系统负载非常低，盼星星盼月亮才出现1个可履行状态的进程。那末进程调度也就不会太重要。哪一个进程可履行，就让它履行去，没有甚么需要多斟酌的。反之，如果系统负载非常高，时时刻刻都有 N 多个进程处于可履行状态，等待被调度运行。那末进程调度程序为了调和这 N 个进程的履行，一定得做很多工作。调和得不好，系统的性能就会大打折扣。这个时候，进程调度就是非常重要的。
虽然我们平常接触的很多计算机（如桌面系统、网络服务器、等）负载都比较低，但是 linux 作为1个通用操作系统，不能假定系统负载低，必须为应付高负载下的进程调度做精心的设计。固然，这些设计对低负载（且没有甚么实时性要求）的环境，没多大用。极端情况下，如果 CPU 的负载始终保持 0 或 1（永久都只有1个进程或没有进程需要在 CPU 上运行），那末这些设计基本上都是徒劳的。
那末，进程的优先级该如何肯定呢？有两种方式：由用户程序指定、由内核的调度程序动态调剂。（下面会说到）
linux 内核将进程分成两个级别：普通进程和实时进程。实时进程的优先级都高于普通进程，除此以外，它们的调度策略也有所不同。
比如斟酌“i++;”这么1句 C 代码。绝大多数情况下，它履行得很快。但是极端情况下还是有这样的可能：
1、i 的内存空间未分配，CPU 触发缺页异常。而 linux 在缺页异常的处理代码中试图分配内存时，又可能由于系统内存紧缺而分配失败，致使进程进入眠眠；
2、代码履行进程中硬件产生中断，linux 进入中断处理程序而搁置当前进程。而中断处理程序的处理进程中又可能产生新的硬件中断，中断永久嵌套不止……；
等等……
而像 linux 这样号称实现了“实时”的通用操作系统，其实只是实现了“软实时”，即尽量地满足进程的实时需求。
如果1个进程有实时需求（它是1个实时进程），则只要它是可履行状态的，内核就1直让它履行，以尽量地满足它对 CPU 的需要，直到它完成所需要做的事情，然后睡眠或退出（变成非可履行状态）。而如果有多个实时进程都处于可履行状态，则内核会先满足优先级最高的实时进程对 CPU 的需要，直到它变成非可履行状态。
因而，只要高优先级的实时进程1直处于可履行状态，低优先级的实时进程就1直不能得到 CPU；只要1直有实时进程处于可履行状态，普通进程就1直不能得到 CPU。
（后来，内核添加了 /proc/sys/kernel/sched_rt_runtime_us和 /proc/sys/kernel/sched_rt_period_us 两个参数，限定了在以 sched_rt_period_us 为周期的时间内，实时进程最多只能运行 sched_rt_runtime_us 这么多时间。这样就在1直有实时进程处于可履行状态的情况下，给普通进程留了1点点能够得到履行的机会。
那末，如果多个相同优先级的实时进程都处于可履行状态呢？这时候就有两种调度策略可供选择：
1、SCHED_FIFO：先进先出。直到先被履行的进程变成非可履行状态，后来的进程才被调度履行。在这类策略下，先来的进程可以履行 sched_yield 系统调用，自愿放弃CPU，以让权给后来的进程；
2、SCHED_RR：轮转调度。内核为实时进程分配时间片，在时间片用完时，让下1个进程使用 CPU；
强调1下，这两种调度策略仅仅针对相同优先级的多个实时进程同时处于可履行状态的情况。
在 linux 下，用户程序可以通过 sched_setscheduler 系统调用来设置进程的调度策略和相干调度参数；sched_setparam 系统调用则只用于设置调度参数。这两个系统调用要求用户进程具有设置进程优先级的能力（CAP_SYS_NICE，1般来讲需要 root 权限）。
通过将进程的策略设为 SCHED_FIFO 或 SCHED_RR，使得进程变成实时进程。而进程的优先级则是通过以上两个系统调用在设置调度参数时指定的。
对实时进程，内核不会试图调剂其优先级。由于进程实时与否？有多实时？这些问题都是跟用户程序的利用场景相干，只有用户能够回答，内核不能臆断。
综上所述，实时进程的调度是非常简单的。进程的优先级和调度策略都由用户定死了，内核只需要总是选择优先级最高的实时进程来调度履行便可。唯1略微麻烦1点的只是在选择具有相同优先级的实时进程时，要斟酌两种调度策略。
与实时进程相比，普通进程的调度要复杂很多。内核需要斟酌两件麻烦事：
1、动态调剂进程的优先级
按进程的行动特点，可以将进程分为“交互式进程”和“批处理进程”：
交互式进程（如桌面程序、服务器、等）主要的任务是与外界交互。这样的进程应当具有较高的优先级，它们总是睡眠等待外界的输入。而在输入到来，内核将其唤醒时，它们又应当很快被调度履行，以做出响应。比如1个桌面程序，如果鼠标点击后半秒种还没反应，用户就会感觉系统“卡”了；
批处理进程（如编译程序）主要的任务是做延续的运算，因此它们会延续处于可履行状态。这样的进程1般不需要高优先级，比如编译程序多运行了几秒种，用户多半不会太在乎；
如果用户能够明确知道进程应当有怎样的优先级，可以通过 nice、setpriority 系统调用来对优先级进行设置。（如果要提高进程的优先级，要求用户进程具有 CAP_SYS_NICE 能力。）
但是利用程序未必就像桌面程序、编译程序这样典型。程序的行动可能5花8门，可能1会儿像交互式进程，1会儿又像批处理进程。以致于用户难以给它设置1个适合的优先级。再者，即便用户明确知道1个进程是交互式还是批处理，也多半碍于权限或由于偷懒而不去设置进程的优先级。（你又是不是为某个程序设置过优先级呢？）因而，终究，辨别交互式进程和批处理进程的重担就落到了内核的调度程序上。
调度程序关注进程近1段时间内的表现（主要是检查其睡眠时间和运行时间），根据1些经验性的公式，判断它现在是交互式的还是批处理的？程度如何？最后决定给它的优先级做1定的调剂。
进程的优先级被动态调剂后，就出现了两个优先级：
1、用户程序设置的优先级（如果未设置，则使用默许值），称为静态优先级。这是进程优先级的基准，在进程履行的进程中常常是不改变的；
2、优先级动态调剂后，实际生效的优先级。这个值是可能时时刻刻都在变化的；
2、调度的公平性
在支持多进程的系统中，理想情况下，各个进程应当是根据其优先级公平地占有 CPU。而不会出现“谁运气好谁占很多”这样的不可控的情况。
linux实现公平调度基本上是两种思路：
1、给处于可履行状态的进程分配时间片（依照优先级），用完时间片的进程被放到“过期队列”中。等可履行状态的进程都过期了，再重新分配时间片；
2、动态调剂进程的优先级。随着进程在CPU上运行，其优先级被不断调低，以便其他优先级较低的进程得到运行机会；
后1种方式有更小的调度粒度，并且将“公平性”与“动态调剂优先级”两件事情合而为1，大大简化了内核调度程序的代码。因此，这类方式同样成为内核调度程序的新宠。
强调1下，以上两点都是仅针对普通进程的。而对实时进程，内核既不能自作多情地去动态调剂优先级，也没有甚么公平性可言。
普通进程具体的调度算法非常复杂，并且随 linux 内核版本的演化也在不断更替（不单单是简单的调剂），所以本文就不继续深入了。有兴趣的朋友可以参考下面的链接：
《Linux 调度器发展简述》
《鼠眼看Linux调度器》
《鼠眼再看Linux调度器［1］》
《鼠眼再看Linux调度器［2］》
在linux 2.4时，可履行状态的进程被挂在1个链表中。每次调度，调度程序需要扫描全部链表，以找出最优的那个进程来运行。复杂度为O(n)；
在linux 2.6初期，可履行状态的进程被挂在N(N=140)个链表中，每个链表代表1个优先级，系统中支持多少个优先级就有多少个链表。每次调度，调度程序只需要从第1个不为空的链表中取出位于链表头的进程便可。这样就大大提高了调度程序的效力，复杂度为O(1)；
在linux 2.6近期的版本中，可履行状态的进程依照优先级顺序被挂在1个红黑树（可以想象成平衡2叉树）中。每次调度，调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。
那末，为何从linux 2.6初期到近期linux 2.6版本，调度程序选择进程时的复杂度反而增加了呢？
这是由于，与此同时，调度程序对公平性的实现从上面提到的第1种思路改变成第2种思路（通过动态调剂优先级实现）。而O(1)的算法是基于1组数目不大的链表来实现的，按我的理解，这使得优先级的取值范围很小（辨别度很低），不能满足公平性的需求。而使用红黑树则对优先级的取值没有限制（可以用32位、 64位、或更多位来表示优先级的值），并且O(logN)的复杂度也还是很高效的。
进程履行系统调用主动变成非可履行状态。比如履行nanosleep进入眠眠、履行exit退出、等等；
进程要求的资源得不到满足而被迫进入眠眠状态。比如履行read系统调用时，磁盘高速缓存里没有所需要的数据，从而睡眠等待磁盘IO；
进程响应信号而变成非可履行状态。比如响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等；
2、抢占。
进程运行时，非预期地被剥夺CPU的使用权。这又分两种情况：进程用完了时间片、或出现了优先级更高的进程。
优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒，或由于释放互斥对象（如释放锁）而被唤醒；
内核在响应时钟中断的进程中，发现当前进程的时间片用完；
内核在响应中断的进程中，发现优先级更高的进程所等待的外部资源的变成可用，从而将其唤醒。比如CPU收到网卡中断，内核处理该中断，发现某个 socket可读，因而唤醒正在等待读这个socket的进程；再比如内核在处理时钟中断的进程中，触发了定时器，从而唤醒对应的正在nanosleep 系统调用中睡眠的进程；
linux 2.4时的设计就非常简单，内核不支持抢占。进程运行在内核态时（比如正在履行系统调用、正处于异常处理函数中），是不允许抢占的。必须等到返回用户态时才会触发调度（确切的说，是在返回用户态之前，内核会专门检查1下是不是需要调度）；
linux 2.6则实现了内核抢占，但是在很多地方还是为了保护临界区资源而需要临时性的禁用内核抢占。
也有1些地方是出于效力斟酌而禁用抢占，比较典型的是spin_lock。spin_lock是这样1种锁，如果要求加锁得不到满足（锁已被别的进程占有），则当前进程在1个死循环中不断检测锁的状态，直到锁被释放。
为何要这样忙等待呢？由于临界区很小，比如只保护“i+=j++;”这么1句。如果由于加锁失败而构成“睡眠-唤醒”这么个进程，就有些得不偿失了。
那末既然当前进程忙等待（不睡眠），谁又来释放锁呢？其实已得到锁的进程是运行在另外一个CPU上的，并且是禁用了内核抢占的。这个进程不会被其他进程抢占，所以等待锁的进程只有可能运行在别的CPU上。（如果只有1个CPU呢？那末就不可能存在等待锁的进程了。）
而如果不由用内核抢占呢？那末得到锁的进程将可能被抢占，因而可能很久都不会释放锁。因而，等待锁的进程可能就不知何年何月得偿所望了。
对1些实时性要求更高的系统，则不能容忍spin_lock这样的东西。宁可改用更费力的“睡眠-唤醒”进程，也不能由于禁用抢占而让更高优先级的进程等待。比如，嵌入式实时linux montavista就是这么干的。
因而可知，实时其实不代表高效。很多时候为了实现“实时”，还是需要对性能做1定妥协的。
2、多处理器下的负载均衡
前面我们并没有专门讨论多处理器对调度程序的影响，其实也没有甚么特别的，就是在同1时刻能有多个进程并行地运行而已。那末，为何会有“多处理器负载均衡”这个事情呢？
如果系统中只有1个可履行队列，哪一个CPU空闲了就去队列中找1个最适合的进程来履行。这样不是很好很均衡吗？
的确如此，但是多处理器共用1个可履行队列会有1些问题。明显，每一个CPU在履行调度程序时都需要把队列锁起来，这会使得调度程序难以并行，可能致使系统性能降落。而如果每一个CPU对应1个可履行队列则不存在这样的问题。
另外，多个可履行队列还有1个好处。这使得1个进程在1段时间内总是在同1个CPU上履行，那末极可能这个CPU的各级cache中都缓存着这个进程的数据，很有益于系统性能的提升。
所以，在linux下，每一个CPU都有着对应的可履行队列，而1个可履行状态的进程在同1时刻只能处于1个可履行队列中。
因而，“多处理器负载均衡”这个麻烦事情就来了。内核需要关注各个CPU可履行队列中的进程数目，在数目不均衡时做出适当调剂。甚么时候需要调剂，以多大力度进程调剂，这些都是内核需要关心的。固然，尽可能不要调剂最好，毕竟调剂起来又要耗CPU、又要锁可履行队列，代价还是不小的。
另外，内核还得关心各个CPU的关系。两个CPU之间，多是相互独立的、多是同享cache的、乃至多是由同1个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要根据。关系越紧密，就应当越能容忍“不均衡”。
更细节的东西可以参考1下关于“调度域”的文章。
3、优先级继承
由于互斥，1个进程（设为A）可能由于等待进入临界区而睡眠。直到正在占有相应资源的进程（设为B）退出临界区，进程A才被唤醒。
可能存在这样的情况：A的优先级非常高，B的优先级非常低。B进入了临界区，但是却被其他优先级较高的进程（设为C）抢占了，而得不到运行，也就没法退出临界区。因而A也就没法被唤醒。
A有着很高的优先级，但是现在却沦落到跟B1起，被优先级其实不太高的C抢占，致使履行被推延。这类现象就叫做优先级反转。
出现这类现象是很不公道的。较好的应对措施是：当A开始等待B退出临界区时，B临时得到A的优先级（还是假定A的优先级高于B），以便顺利完成处理进程，退出临界区。以后B的优先级恢复。这就是优先级继承的方法。
为了实现优先级继承，内核又得做很多事情。更细节的东西可以参考1下关于“优先级反转”或“优先级继承”的文章。
4、中断处理线程化
在linux下，中断处理程序运行于1个不可调度的上下文中。从CPU响应硬件中断自动跳转到内核设定的中断处理程序去履行，到中断处理程序退出，全部进程是不能被抢占的。
1个进程如果被抢占了，可以通过保存在它的进程控制块（task_struct）中的信息，在以后的某个时间恢复它的运行。而中断上下文则没有task_struct，被抢占了就没法恢复了。
中断处理程序不能被抢占，也就意味着中断处理程序的“优先级”比任何进程都高（必须等中断处理程序完成了，进程才能被履行）。但是在实际的利用场景中，可能某些实时进程应当得到比中断处理程序更高的优先级。
因而，1些实时性要求更高的系统就给中断处理程序赋予了task_struct和优先级，使得它们在必要的时候能够被高优先级的进程抢占。但是明显，做这些工作是会给系统造成1定开消的，这也是为了实现“实时”而对性能做出的1种妥协。
更多细节可以参考1下关于“中断线程化”的文章。
转自：linux 进程调度浅析
下一篇 人月神话之削足适履札记