linux调度机制(cpu调度器)

linux调度算法的核心思想是什么

第一部分：实时调度算法

什么是实时系统，POSIX 1003.b作了这样的定义：是指系统可以在有限响应时间内提供所需的服务级别。较可取被定义为由Donald乔利士的的：一个实时系统的程序的逻辑正确性不仅取决于计算的准确度，而且还对结果，如果系统时间的限制不能满足将是一个系统错误发生。

基于实时系统的实时性要求的不同，可分为软实时和硬实时两种。硬实时系统是指系统必须确保，在最坏情况下的服务时间，截止日期为事件的响应时间是在任何情况下，必须满足。如航天飞船的控制是这样一个系统的现实。所有其他实时系统的特点，可以称为软实时系统。如果清除，软实时系统是那些从统计学的角度来看，一个任务（在下面的讨论中，我们将有任务和过程不作出区分），以确保系统的处理时间，可以得到事件可以处理的最后期限到来之前，违反的最后期限，并不会带来一个致命的错误，如实时多媒体系统是一种软实时系统。

一台电脑系统的CPU和其他资源进行有效的调度和管理，以提供实时操作系统的支持。的多任务的实时系统中，资源的调度和管理更复杂的。下面讨论本文将从各种实时任务调度算法的分类的角度来看，普通的Linux操作系统进程调度和各种实时Linux系统，然后研究，以支持实时特点，普通的Linux系统的改进。实时领域的一些问题，并总结了各种实时Linux的Linux操作系统，归根到底是如何解决这些问题。

CPU的实时调度算法的分类

多种实时操作系统的实时调度算法可以分为以下三类Wang99] [Gopalan01]：基于优先级调度算法（优先级驱动调度PD），基于在共享的CPU使用率调度算法（分享驱动调度SD）的比例，以及基于时间的进程调度算法（时间驱动调度TD），下面这三种调度算法逐一介绍。

1.1

/>基于优先级的调度算法，基于优先级的调度算法，每个进程被分配一个优先级，每次的进程调度程序，调度程序总是具有最高的调度优先级的任务执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为以下两种类型的Krishna01] [Wang99]：静态优先级调度算法

该算法得到这些系统中运行的所有进程都静态分配一个优先级。静态优先级分配的属性的应用程序，如任务循环中的用户优先级，或其他预先确定的政策。 RM（速率单调）的调度算法是一个典型的静态优先级的调度算法，根据执行的任务的调度优先级的周期的长度确定，那些具有小的执行周期的任务的优先级较高。

动态优先级调度算法：

该算法基于任务的资源需求动态地分配任务的优先级，资源分配和调度的目的更大的灵活性。非实时系统，这种算法有很多，如短作业优先级调度算法。任务的实时调度算法，EDF算法是使用最广泛的动态优先级调度算法，该算法根据他们的截止日期（截止日期）分配优先级的就绪队列中的每个任务，最近期限具有最高的优先级。

1.2

基于优先级调度算法的调度算法是简单而有效的，但这种算法的基础上按比例份额是一个硬实时调度，许多的情况下，不适合使用此算法：例如，软实时应用，如实时多媒体会议系统。对于软实时应用程序，共享资源调度算法（SD算法）的比例使用是更合适的。

比例共享调度算法是指对CPU使用率的比例共享调度算法，其基本思路是按照一定的权重（比率），需要一组调度安排任务，以使它们的权重成比例的执行时间。

要实现比例共享调度算法[Nieh01]有两种方法：第一种方法是调整的准备过程中出现的调度队列队第一频率，并安排一线队的过程中，执行第二种方法是连续调度进程就绪队列中投产，但根据调整分配一个进程的运行时间片分配的权重。

比例共享调度算法可以分为以下类别：循环赛，公平份额，公平排队，的彩票调度方法，（彩票）。

比例共享调度算法的一个问题是，它并没有定义任何优先的概念，所有的任务都根据其应用的CPU资源的比例共享系统过载时，执行的所有任务将较慢比例。因此，为了确保该系统的实时过程中获得一定量的CPU处理时间，一般采用的是动态权重的调整过程。

1.3。基于时间进程调度算法的调度算法

对于那些具有稳定，简单的系统已知输入，您可以使用时间驱动（驱动时间时间：TD）数据处理，它可以提供一个良好的预测。这种调度算法本质上是一个设计定型的离线静态调度方法。在系统的设计阶段，所有处理的情况下，在明确的制度，每个任务切换的开始和结束的时间提前做出了明确的安排和设计。该算法是适用于小型嵌入式系统，自动化控制系统，传感器和其他应用环境。

该算法的优势是良好的可预测性任务的执行，但最大的缺点是缺乏灵活性，而且会有一个任务需要执行，而CPU保持空闲。

一般的Linux系统CPU调度

一般的Linux系统支持实时和非实时两种进程，实时进程与普通进程方面具有绝对的优先权。相应地，实时进程调度策略SCHED_FIFO或SCHED_RR，普通进程SCHED_OTHER调度策略。

每个任务调度算法的实现在Linux四种调度参数，它们是rt_priority优先政策（尼斯），计数器。调度进程调度的基础上，这四个参数。

SCHED_OTHER调度策略，调度程序总是会选择优先级+计数器的值进程调度的执行。从逻辑分析存在SCHED_OTHER调度策略调度处理来执行，其特征在于，所述优先级是一个固定的调度周期（历元），在每个调度周期内的过程中的优先级，计数器的值的大小的影响这一刻已经确定变量值的过程中被创建时，它代表了进程的优先级，也代表数量的时间片，通过该方法可以得到在每个调度周期内，计数器是一个动态值，它反映了当前调度周期的过程中，剩余的时间片。在每个调度周期的开始，分配给优先级值计数器，那么每一次进程被调度运行计数器的值？减少。当计数器的值是零，这个过程已经运行的时间片调度期内，不再参与调度周期进程调度。当所有的进程都用完了时间片调度期结束，然后一遍又一遍。此外，可以看出在Linux系统中的调度周期是不固定的，它的量是动态变化的，例如，在运行的进程的数目和它们的优先级值？可以影响一个划时代的长度。有一点值得注意的是，在2.4内核中，首要任务是不错的替换两个类似的作用。

按比例分担的调度策略调度策略SCHED_OTHER可见的性质，它的这种设计方法，以确保进程调度的公平性-一个低优先级进程，在每个时代也将得到他们的份额那些CPU的执行时间，此外，它也提供了不同的进程的优先级，进程执行时间可以得到更多的具有高优先级值。

对于实时的过程中，他们使用基于实时优先级rt_priority的优先级调度策略，但相同的实时优先级的进程调度方法是根据不同的调度策略，

BR/> SCHED_FIFO：不同的进程，根据静态优先级排队，然后在相同的优先级队列，先准备好运行的第一谁调度和运行的进程不会被终止，直到发生以下情况：1。高优先级的进程篡夺了CPU;自己的资源请求受阻;自己主动放弃CPU（呼叫SCHED_YIELD）;

SCHED_RR是这样的：这个调度策略SCHED_FIFO与上述完全相同，除了时间片分配给每个进程，正在实施的过程中，给执行时间片，时间片的长度可以通过sched_rr_get_interval调用

由于Linux系统本身是一个桌面导向的系统，因此，它是用于在实时应用中的一些问题：/>/> Linux系统调度单位是10ms，所以它不能提供精确的定时中断; p>当一个进程调用系统调用进入内核模式运行，它不能被抢占;

Linux内核实现大量采用了封闭中断操作损失;

由于使用虚拟内存技术，当发生页面错误时，从硬盘中读取的数据交换的需要，但硬盘读取和写入的存储位置的随机性，将导致随机读取和写入时间，这在某些情况下，会影响实时任务期限;

虽然Linux的进程调度器还支持实时优先级，但由于缺乏有效的实时任务调度机制和调度算法;其网络子协议处理和其它设备的中断处理，调度伴有相应的过程和自己的有没有明确的调度机制;

各种实时Linux系统

Home>的的

3.1 RT-Linux和RTAI

RT-Linux是新墨西哥大学的研究（新墨西哥州技术学院）[RTLinuxWeb] [Barabanov97。其基本思路是，在Linux系统上的硬实时支持，它实现了一个微内核实时操作系统（也被称为RT-Linux的实时子系统），而普通的Linux系统作为一个低优先级任务在操作系统中运行。在正常的Linux系统的另一个任务可以沟通，通过FIFO和实时任务。 RT-Linux的框架如图1所示：

图1 RT-Linux的结构

RT-Linux的关键技术是软件模拟硬件中断控制器。当Linux系统不时阻止CPU中断，实时定量RT-Linux的子系统的请求拦截，爱不释手，而事实上并没有真正阻止硬件中断，从而避免了由于中断造成的封由系统在一段时间内没有响应，从而在改进的实时。当传递给Linux内核的RT-Linux的一个硬件中断到达截取的中断，并确定是否有一个实时子系统中断例程来处理或处理。此外，的最小定时的精度在正常的Linux系统是确定系统的实时时钟的频率，Linux的系统时钟被设置到时钟中断每秒100，所以在Linux的系统定时的精度10毫秒，即时钟周期10ms时，RT-Linux的实时时钟设置为单触发状态，可以提供更多的十几微秒调度粒度。

RT-Linux实时子系统的任务调度优先级驱动算法，RM，EDF等，也可用于其他调度算法。

RT-Linux的专有系统，重型工作，的确是一个不错的选择，但他只提供了CPU资源的调度和实时系统和Linux系统的关系不是非常密切，因此开发人员可以充分利用已在Linux系统中，如协议栈实现的功能。 RT-Linux的工业控制等实时任务简单和硬实时要求的环境，但大量的工作需要做，如果你想应用的多媒体处理。

意大利实时应用程序接口（RTAI）来自RT-Linux的，它是在设计和RT-Linux的思想相同。这是原来的设计中，为了解决问题，RT-Linux的不同版本的Linux之间很难很难移植，RTAI在Linux上定义的实时硬件抽象层，这个抽象层接口提供实时任务Linux系统的相互作用，这可以增加一点可以Linux内核源代码到Linux内核的实时支持。

3.2。 KURT-Linux的

KURT-Linux的堪萨斯大学开发的，它可以提供实时微秒精度[KurtWeb] [斯里尼瓦桑]。与RT-Linux的单独实现一个实时内核，KURT-Linux是常用的Linux系统的基础上实现的，这也是第一个基于Linux的实时系统可以使用普通的Linux系统调用。

KURT-Linux系统分为三种状态：正常状态，实时状态和混合状态，在正常状态下，它使用普通的Linux实时运行状态实时调度策略任务，实时和非实时任务的混合状态，可以执行实时状态可以被用来为实时的要求更加严格。

为了提高Linux系统的实时特性，有必要提高精度的时钟系统的支持。但是，如果只是简单地增加时钟频率将导致调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾，KURT-Linux中使用的时钟精度的方法[UTIMEWeb]提高Linux系统UTIME，时钟芯片设置为单次触发状态（单拍模式），也就是每个时钟芯片设置超时，然后再次超时事件发生时，在时钟中断的处理程序所需的时钟芯片设置一个超时。其基本思想是一个精确的时间意味着我们需要的时钟中断发生时，我们需要一个更精确的时间，以达到这样的精度，但并不一定需要系统时钟频率。它采用了CPU时钟计数器时间戳计数器（TSC）提供准确的CPU频率精度的时间。

KURT-Linux的实时任务调度，使用静态CPU的实时调度算法，基于时间（TD）。实时任务需要实时事件发生在设计阶段就必须清楚列明。该算法可以实现更好的调度任务，对于那些谁周期。

KURT-Linux的相RT-Linux的优势之一是，你可以使用系统调用的Linux系统，它最初是专为硬实时支持，但因为它是简单的实现将使用一个简单的时间驱动调度取代Linux的调度，实时进程调度的影响等非实时任务，在某些情况下会发生实时任务的截止日期是脆弱的不符合的，也被称为严格的实时系统（快地实时）。基于KURT-Linux的应用程序：艺术（ATM参考交通系统），多媒体播放软件。 KURT-Linux的另一种方法，需要频繁的时钟芯片编程。

3.3。 RED-Linux的

RED-Linux是加州大学尔湾，实时Linux系统的发展[REDWeb] [Wang99]，它将支持实时调度和Linux实现相同的操作系统内核。它支持三种类型的调度算法，即：时间驱动优先Dirven，分享驱动。

为了提高系统的调度粒度，RED-Linux的学习RT-Linux的软件模拟中断的管理机制，并增加频率的时钟中断。 RED-Linux的中断仿真程序只是简单地中断会在队列中排队一个硬件中断到来时，并没有进行实际的中断处理程序。

另外，为了解决Linux的内核模式的过程中不能被中断，RED-Linux的插入Linux内核抢占点原语的众多功能，使这一进程在内核模式下，也在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标是提供常规调度框架可以支持多种调度算法，系统为每个任务增加几个属性，进程调度的基础上：

优先级：作业的优先级;

开始时间：工作的开始时间;

完成时间：工作的结束时间; BR p>预算：资源的数量在操作过程中要使用的工作;

调整值？这些属性和调度根据什么优先使用的这些属性值几乎所有的调度算法。在这种情况下，三种不同的调度算法无缝地一起耦合到一个统一的。

Linux 进程调度

Linux的调度策略区分实时进程和普通进程，实时进程的调度策略是SCHED_FIFO和SCHED_RR，普通的，非实时进程的调度策略是SCHED_NORMAL（SCHED_OTHER）。

实时调度策略被实时调度器管理，普通调度策略被完全公平调度器来管理。实时进程的优先级要高于普通进程（nice越小优先级越高）。

SCHED_FIFO实现了一种简单的先入先出的调度算法，它不使用时间片，但支持抢占，只有优先级更高的SCHED_FIFO或者SCHED_RR进程才能抢占它，否则它会一直执行下去，低优先级的进程不能抢占它，直到它受阻塞或自己主动释放处理器。

SCHED_RR是带有时间片的一种实时轮流调度算法，当SCHED_RR进程耗尽它的时间片时，同一优先级的其它实时进程被轮流调度，时间片只用来重新调用同一优先级的进程，低优先级的进程决不能抢占SCHED_RR任务，即使它的时间片耗尽。SCHED_RR是带时间片的SCHED_FIFO。

Linux的实时调度算法提供了一种软实时工作方式，软实时的含义是尽力调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求，相反，硬实时系统保证在一定的条件下，可以满足任何调度的要求。

SCHED_NORMAL使用完全公平调度算法（CFS），之前的算法直接将nice值对应时间片的长度，而在CFS中，nice值只作为进程获取处理器运行比的权重，每个进程都有一个权重，nice优先级越高，权重越大，表示应该运行更长的时间。Linux的实现中，每个进程都有一个vruntime字段，vruntime是经过量化的进程运行时间，也就是实际运行时间除以权重，所以每个量化后的vruntime应该相等，这就体现了公平性。

CFS当然也支持抢占，但与实时调度算法不同，实时调度算法是根据优先级进行抢占，CFS是根据vruntime进行抢占，vruntime小就拥有优先被运行的权利。

为了计算时间片，CFS算法需要为完美多任务中的无限小调度周期设定近似值，这个近似值也称作目标延迟，指每个可运行进程在目标延迟内都会调度一次，如果进程数量太多，则时间粒度太小，所以约定时间片的默认最小粒度是1ms。

进程可以分为I/O消耗型和处理器消耗型，这两种进程的调度策略应该不同，I/O消耗型应该更加实时，给对端的感觉是响应很快，同时它一般又不会消耗太多的处理器，因而I/O消耗型需要调度频繁。相对来说，处理器消耗型不需要特别实时，应该尽量降低它的调度频度，延长其运行时间。

参考： linux内核分析——CFS（完全公平调度算法）-一路向北你好-博客园

Linux系统中的进程调度介绍

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

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

而进程调度究竟有多重要呢?首先，我们需要明确一点：进程调度是对TASK_RUNNING状态的进程进行调度(参见《linux进程状态浅析》)。如果进程不可执行(正在睡眠或其他)，那么它跟进程调度没多大关系。

所以，如果你的系统负载非常低，盼星星盼月亮才出现一个可执行状态的进程。那么进程调度也就不会太重要。哪个进程可执行，就让它执行去，没有什么需要多考虑的。

反之，如果系统负载非常高，时时刻刻都有N多个进程处于可执行状态，等待被调度运行。那么进程调度程序为了协调这N个进程的执行，必定得做很多工作。协调得不好，系统的性能就会大打折扣。这个时候，进程调度就是非常重要的。

尽管我们平常接触的很多计算机(如桌面系统、网络服务器、等)负载都比较低，但是linux作为一个通用操作系统，不能假设系统负载低，必须为应付高负载下的进程调度做精心的设计。

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

优先级

现在的操作系统为了协调多个进程的“同时”运行，最基本的手段就是给进程定义优先级。定义了进程的优先级，如果有多个进程同时处于可执行状态，那么谁优先级高谁就去执行，没有什么好纠结的了。

那么，进程的优先级该如何确定呢?有两种方式：由用户程序指定、由内核的调度程序动态调整。(下面会说到)

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

实时进程的调度

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

这样的“实时”称为“硬实时”，多用于很精密的系统之中(比如什么火箭、导弹之类的)。一般来说，硬实时的系统是相对比较专用的。

像linux这样的通用操作系统显然没法满足这样的要求，中断处理、虚拟内存、等机制的存在给处理时间带来了很大的不确定性。硬件的cache、磁盘寻道、总线争用、也会带来不确定性。

比如考虑“i++;”这么一句C代码。绝大多数情况下，它执行得很快。但是极端情况下还是有这样的可能：

1、i的内存空间未分配，CPU触发缺页异常。而linux在缺页异常的处理代码中试图分配内存时，又可能由于系统内存紧缺而分配失败，导致进程进入睡眠;

2、代码执行过程中硬件产生中断，linux进入中断处理程序而搁置当前进程。而中断处理程序的处理过程中又可能发生新的硬件中断，中断永远嵌套不止……;

等等……

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

如果一个进程有实时需求(它是一个实时进程)，则只要它是可执行状态的，内核就一直让它执行，以尽可能地满足它对CPU的需要，直到它完成所需要做的事情，然后睡眠或退出(变为非可执行状态)。

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

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

那么，如果多个相同优先级的实时进程都处于可执行状态呢?这时就有两种调度策略可供选择：

1、SCHED_FIFO：先进先出。直到先被执行的进程变为非可执行状态，后来的进程才被调度执行。在这种策略下，先来的进程可以执行sched_yield系统调用，自愿放弃CPU，以让权给后来的进程;

2、SCHED_RR：轮转调度。内核为实时进程分配时间片，在时间片用完时，让下一个进程使用CPU;

强调一下，这两种调度策略以及sched_yield系统调用都仅仅针对于相同优先级的多个实时进程同时处于可执行状态的情况。

在linux下，用户程序可以通过sched_setscheduler系统调用来设置进程的调度策略以及相关调度参数;sched_setparam系统调用则只用于设置调度参数。这两个系统调用要求用户进程具有设置进程优先级的能力(CAP_SYS_NICE，一般来说需要root权限)(参阅capability相关的文章)。

通过将进程的策略设为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系统调用中睡眠的进程。

所有任务都采用linux分时调度策略时：

1，创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。

2，将根据每个任务的nice值确定在cpu上的执行时间(counter)。

3，如果没有等待资源，则将该任务加入到就绪队列中。

4，调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算权值(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

5，此时调度程序重复上面计算过程，转到第4步。

6，当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

所有任务都采用FIFO时：

1，创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。

2，如果没有等待资源，则将该任务加入到就绪队列中。

3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。

4，调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。

5，如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。

所有任务都采用RR调度策略时：

1，创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。

2，如果没有等待资源，则将该任务加入到就绪队列中。

3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。

4，如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。

5，当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。

系统中既有分时调度，又有时间片轮转调度和先进先出调度：

1，RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。

2，当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。

3，RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性(优先级是一样的，为什么要让你一直运行?),如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行，保证了公平。

Ingo Molnar-实时补丁

为了能并入主流内核，Ingo Molnar的实时补丁也采用了非常灵活的策略，它支持四种抢占模式：

1.No Forced Preemption(Server)，这种模式等同于没有使能抢占选项的标准内核，主要适用于科学计算等服务器环境。

2.Voluntary Kernel Preemption(Desktop)，这种模式使能了自愿抢占，但仍然失效抢占内核选项，它通过增加抢占点缩减了抢占延迟，因此适用于一些需要较好的响应性的环境，如桌面环境，当然这种好的响应性是以牺牲一些吞吐率为代价的。

3.Preemptible Kernel(Low-Latency Desktop)，这种模式既包含了自愿抢占，又使能了可抢占内核选项，因此有很好的响应延迟，实际上在一定程度上已经达到了软实时性。它主要适用于桌面和一些嵌入式系统，但是吞吐率比模式2更低。

4.Complete Preemption(Real-Time)，这种模式使能了所有实时功能，因此完全能够满足软实时需求，它适用于延迟要求为100微秒或稍低的实时系统。

实现实时是以牺牲系统的吞吐率为代价的，因此实时性越好，系统吞吐率就越低。