大家好，我是本期栏目编辑小友，现在为大家讲解Linux 进程调度浅析问题。
为了在操作系统中实现多进程，进程调度是必不可少的。进程调度是在TASK_RUNNING状态下调度进程。如果一个进程不可执行(休眠或其他)，它与进程调度没有什么关系。
因此，如果你的系统负载很低，期待星星和月亮有一个可执行的过程。那么流程调度就不那么重要了。哪个流程可以执行，就让它执行，没什么好考虑的。
相反，如果系统负载很高，则始终有n个以上的进程处于可执行状态，等待调度运行。那么为了协调这N个进程的执行，进程调度器必须做大量的工作。如果协调不好，系统的性能会大大降低。此时，流程调度非常重要。
虽然很多电脑(如桌面系统、网络服务器等。)我们通常接触到的都有相对较低的负载，linux作为通用操作系统，不能假设系统负载较低，而必须精心设计以应对高负载下的进程调度。
当然，这些设计在低负载(并且没有实时要求)环境中用处不大。在极端情况下，如果CPU负载总是0或1(总是只有一个进程或没有进程在CPU上运行)，那么这些设计基本上是徒劳的。
优先
为了协调多个进程的“同时”操作，当前操作系统最基本的手段是为进程定义优先级。定义了流程的优先级。如果多个进程同时处于可执行状态，那么优先级最高的进程就会执行。没什么好担心的。
那么，如何确定流程的优先级呢？有两种方式：由用户程序指定和由内核调度程序动态调整。(将在下面提到)
linux内核将进程分为两个层次：普通进程和实时进程。实时进程的优先级高于普通进程。此外，它们的调度策略也不同。
实时进程的调度。
实时，原意是“给定的操作必须在一定时间内完成”。关键不在于必须以多快的速度处理操作，而在于时间应该是可控的(在最坏的情况下，不能超过给定的时间)。
这样的“实时”被称为“硬实时”，多用于非常精密的系统(如火箭、导弹)。一般来说，硬实时系统相对专用。
像linux这样的通用操作系统显然不能满足这一要求，中断处理、虚拟内存等机制的存在给处理时间带来了很大的不确定性。硬件缓存、磁盘寻道和总线争用也会带来不确定性。
考虑“我”；比如说。这样的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 _ runTIme _ us的时间和sched _ rt _ period _ us一样长。这样，在实时进程始终处于可执行状态的情况下，给普通进程留下一点执行的机会。)
那么，如果多个具有相同优先级的实时进程处于可执行状态呢？有两种调度策略可供选择：
1.SCHED_FIFO:先进先出。直到第一个执行的进程变得不可执行，后面的进程才被安排执行。在这种策略下，第一个进程可以进行sched_yield系统调用，并主动放弃CPU给后面的进程供电。
2.SCHED_RR:循环调度。内核为实时进程分配一个时间片，当时间片用完时，让下一个进程使用CPU。
强调这两种调度策略只针对多个优先级相同的实时进程同时处于可执行状态的情况。
在linux下，用户程序可以通过调用sched_setscheduler系统来设置进程的调度策略和相关的调度参数。Sched_setparam系统调用仅用于设置调度参数。这两个系统调用要求用户进程能够设置进程优先级(CAP_SYS_NICE，一般需要root权限)。
通过将进程的策略设置为SCHED_FIFO或SCHED_RR，进程就变成了一个实时进程。当通过上述两个系统调用设置调度参数时，指定进程的优先级。
对于实时进程，内核不会试图调整它们的优先级。因为过程是实时的？实时性如何？这些问题都与用户程序的应用场景有关，只有用户可以回答，但内核不能做假设。
总而言之，实时进程的调度非常简单。进程的优先级和调度策略由用户决定，内核只需要一直选择。
优先级最高的实时进程来调度执行即可。唯一稍微麻烦一点的只是在选择具有相同优先级的实时进程时，要考虑两种调度策略。普通进程的调度
实时进程调度的中心思想是，让处于可执行状态的最高优先级的实时进程尽可能地占有CPU，因为它有实时需求；而普通进程则被认为是没有实时需求的进程，于是调度程序力图让各个处于可执行状态的普通进程和平共处地分享CPU，从而让用户觉得这些进程是同时运行的。
与实时进程相比，普通进程的调度要复杂得多。内核需要考虑两件麻烦事：
一、动态调整进程的优先级
按进程的行为特征，可以将进程分为“交互式进程”和“批处理进程”：
交互式进程（如桌面程序、服务器、等）主要的任务是与外界交互。这样的进程应该具有较高的优先级，它们总是睡眠等待外界的输入。而在输入到来，内核将其唤醒时，它们又应该很快被调度执行，以做出响应。比如一个桌面程序，如果鼠标点击后半秒种还没反应，用户就会感觉系统“卡”了；
批处理进程（如编译程序）主要的任务是做持续的运算，因而它们会持续处于可执行状态。这样的进程一般不需要高优先级，比如编译程序多运行了几秒种，用户多半不会太在意；
如果用户能够明确知道进程应该有怎样的优先级，可以通过nice、setpriority（非实时进程优先级的设置）系统调用来对优先级进行设置。（如果要提高进程的优先级，要求用户进程具有CAP_SYS_NICE能力。
然而应用程序未必就像桌面程序、编译程序这样典型。程序的行为可能五花八门，可能一会儿像交互式进程，一会儿又像批处理进程。以致于用户难以给它设置一个合适的优先级。再者，即使用户明确知道一个进程是交互式还是批处理，也多半碍于权限或因为偷懒而不去设置进程的优先级。（你又是否为某个程序设置过优先级呢？）
于是，最终，区分交互式进程和批处理进程的重任就落到了内核的调度程序上。
调度程序关注进程近一段时间内的表现（主要是检查其睡眠时间和运行时间），根据一些经验性的公式，判断它现在是交互式的还是批处理的？程度如何？最后决定给它的优先级做一定的调整。
进程的优先级被动态调整后，就出现了两个优先级：
1、用户程序设置的优先级（如果未设置，则使用默认值），称为静态优先级。这是进程优先级的基准，在进程执行的过程中往往是不改变的；2、优先级动态调整后，实际生效的优先级。这个值是可能时时刻刻都在变化的；
二、调度的公平性
在支持多进程的系统中，理想情况下，各个进程应该是根据其优先级公平地占有CPU。而不会出现“谁运气好谁占得多”这样的不可控的情况。
linux实现公平调度基本上是两种思路：
1、给处于可执行状态的进程分配时间片（按照优先级），用完时间片的进程被放到“过期队列”中。等可执行状态的进程都过期了，再重新分配时间片；2、动态调整进程的优先级。随着进程在CPU上运行，其优先级被不断调低，以便其他优先级较低的进程得到运行机会；后一种方式有更小的调度粒度，并且将“公平性”与“动态调整优先级”两件事情合而为一，大大简化了内核调度程序的代码。因此，这种方式也成为内核调度程序的新宠。
强调一下，以上两点都是仅针对普通进程的。而对于实时进程，内核既不能自作多情地去动态调整优先级，也没有什么公平性可言。
普通进程具体的调度算法非常复杂，并且随linux内核版本的演变也在不断更替（不仅仅是简单的调整），所以本文就不继续深入了。
调度程序的效率
“优先级”明确了哪个进程应该被调度执行，而调度程序还必须要关心效率问题。调度程序跟内核中的很多过程一样会频繁被执行，如果效率不济就会浪费很多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时的设计就非常简单，内核不支持抢占。进程运行在内核态时（比如正在执行系统调用、正处于异常处理函数中），是不允许抢占的。必须等到返回用户态时才会触发调度（确切的说，是在返回用户态之前，内核会专门检查一下是否需要调度）；
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以及优先级，使得它们在必要的时候能够被高优先级的进程抢占。但是显然，做这些工作是会给系统造成一定开销的，这也是为了实现“实时”而对性能做出的一种让步。
标签：
版权声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢您的支持与理解。