皮皮网

1.记一次操作系统实验（处理机调度）
2.linux进程/线程调度策略(SCHED_OTHER,进进程SCHED_FIFO,SCHED_RR)
3.Linux 进程调度
4.关于Linux的调度！！程调！度源调度
5.从Linux内核源码的源码角度深入解释进程（图例解析）
6.Linux 调度器BFS 实现原理

记一次操作系统实验（处理机调度）

       在操作系统实验中，我通过一系列实验，分析探索了Linux系统下的进进程枫叶红源码进程调度与通信机制。以下是程调对各实验步骤的总结与记录。

       实验一：调整进程优先级以控制CPU资源分配。度源调度使用nice命令改变进程优先级，源码使进程1优先级为，分析进程2为-，进进程通过top和/proc/PID/sched展示进程调度策略与优先级变化，程调确保进程1使用约1/5，度源调度进程2使用约4/5的源码CPU资源。

       实验二：在双核系统下实现负载均衡。分析通过修改虚拟机配置，模拟单核与双核环境，使用nice调整进程优先级，实现P1/P3在第一处理器上各占%，P2/P4在第二处理器上，分别占%和%。记录进程在不同处理器上的绑定情况，使用top命令监控CPU资源分配。创建第五个进程进行负载均衡测试，记录各进程处理器核间的迁移次数。

       实验三：RR实时调度下实现进程优先级抢占。运行具有相同优先级的RR进程与更高优先级的FIFO进程，使用top和/proc/PID/sched展示进程调度策略与优先级，观察FIFO进程如何抢占CPU资源，同时记录两个RR进程的轮流执行情况。

       实验四：设计生产者-消费者模式的程序。编写生产者进程，将“一整行”按键信息保存至共享内存，并等待消费者进程读取；消费者进程生成两个线程，同时读取并清空缓冲区，其间加入时延以观察同步效果。在两个终端窗口运行程序，确保一次只有一个进程操作缓冲区，使用posix信号量与互斥量实现生产者与消费者的同步，记录各进程/线程完成通信的操作过程，通过/proc文件系统和ipcs命令监控共享内存、信号量与进程阻塞状态。

linux进程/线程调度策略(SCHED_OTHER,SCHED_FIFO,SCHED_RR)

       Linux内核的三种调度策略分别是SCHED_OTHER、SCHED_FIFO和SCHED_RR。SCHED_OTHER通常用于分时进程，通过nice值和counter值决定进程的调度优先级。nice值越小，counter值越大，进程被调度的概率越大。反之，进程曾经使用CPU最少时会得到优先调度。SCHED_FIFO策略中，一旦进程占用CPU，它将一直运行直到更高优先级的任务到达或主动放弃。相比之下，SCHED_RR策略允许每个任务执行一段时间后让出CPU，这保证了所有具有相同优先级的RR任务的调度公平性。

       SCHED_RR与SCHED_FIFO的调度策略存在显著差异。SCHED_RR策略在时间片用完后将重新分配时间片并置于就绪队列尾部，确保了所有具有相同优先级的RR任务公平地获得执行机会。而SCHED_FIFO策略一旦占用CPU，该进程会一直运行直到有更高优先级的任务到达或主动放弃，这可能导致进程的运行时间过长，甚至在没有更高优先级任务的情况下一直占用CPU。

       所有任务采用分时调度策略（SCHED_OTHER）时，创建任务时指定采用此策略，并设置nice值（范围为-到）。系统根据每个任务的nice值确定其在CPU上的执行时间，并将任务加入就绪队列。调度程序遍历就绪队列，通过计算counter+-nice结果，选择权值最大的任务执行。当时间片用完或主动放弃CPU时，任务将重新加入就绪队列末尾。如果所有任务的权值不大于0，则重新创建任务。源码是什么作用

       当所有任务采用FIFO调度策略（SCHED_FIFO）时，创建进程时指定使用FIFO，并设置实时优先级（范围为1到）。任务如果没有等待资源，则加入就绪队列。调度程序遍历队列，选择权值最高的实时优先级任务使用CPU。任务将一直占用CPU直到有更高优先级任务到达或主动放弃。如果当前任务等待资源而主动放弃CPU，它将从就绪队列中删除并加入等待队列。

       当所有任务采用RR调度策略（SCHED_RR）时，创建任务时指定RR策略，并设置实时优先级和nice值。如果没有等待资源，任务加入就绪队列。调度程序遍历队列，选择权值最高的任务使用CPU。如果RR任务的时间片为0，将根据nice值设置新时间片，并将任务放入就绪队列末尾。如果任务等待资源而主动放弃CPU，它将从就绪队列中删除并加入等待队列。

       在系统中，既有分时调度（SCHED_OTHER），又有时间片轮转调度（SCHED_RR）和先进先出调度（SCHED_FIFO）。分时调度主要用于非实时进程，而实时进程则倾向于采用SCHED_FIFO或SCHED_RR。当实时进程准备就绪时，如果CPU正在运行非实时进程，实时进程会立即抢占非实时进程。RR和FIFO进程都采用实时优先级作为调度权值标准，RR可以看作是FIFO的一个扩展。在FIFO中，如果两个进程的优先级相同，它们在队列中的顺序决定了执行顺序，这可能导致不公正。将两个优先级相同的任务的调度策略都设为RR，可以保证这两个任务循环执行，确保公平性。

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的调度！！！

       进程调度策略就是调度系统种哪一个进程来CPU运行。这种调度分2层考虑。

       第一层，进程状态这个是最优先考虑的，也就是说优先级最高的。在linux中只有就绪态的进程才有可能会被调度选中然后占有CPU，其它状态的进程不可能占有的到CPU。下面是linux中进程的状态

       TASK_RUNNING:就绪状态，得到CPU就可以运行。

       TASK_INTERRUPTIBLE:浅度睡眠，资源到位或者受到信号就会变成就绪态。

       TASK_UNINTERRUPTIBLE:深度睡眠，资源到位就会进入就绪态，不响应信号。

       TASK_ZOMBIE：僵死态，进程exit后。

       TASK_STOPPED：暂停态，收到SIG_CONT信号进入就绪态。

       第二层，其实真正在操作系统中的实现，就是所有就绪态进程链接成一个队列，进程调度时候只会考虑这个队列中的进程，对其它的进程不考虑，这就实现了第一层中的要求。接下来就是就绪队列内部各个进程的竞争了。

       Linux采用3种不同的调度政策，SCHED_FIFO（下面简写成FIFO，先来先服务），SCHED_RR（简写成RR，时间片轮流），SCHED_OTHER（下面简写成OTHER）。这里大家就能看出一个问题，采用同等调度政策的frm是源码吗进程之间自然有可比性，Linux3种调度政策并存，那么不同调度政策间的进程如何比较呢？可以说他们之间根本就没有可比性。其实在调度时候，调度只看一个指标，那就是各个进程所具有的权值，权值最大的且在可执行队列中排在最前面的就会被调度执行。而权值的计算才会设计到各方面因素，其中调度政策可以说在计算权值中，份量是最重的。

       为什么Linux要这么干呢？这是由于事务的多样性决定的，进程有实时性进程和非实时性的进程2种，FIFO和RR是用来支持实时性进程的调度，我们看一下这3种政策下权值的计算公式就明白了：

       FIFO和RR计算公式，权值=+进程真正的运行时间

       OTHER计算公式，当时间片为0时，权值=0.当时间片不为0时候，权值=剩余时间片+-nice,同时如果是内核线程有+1的小加分，这是因为内核线程无需用户空间的切换，所以给它加了一分，奖励他在进程切换时候开销小的功劳。时间片好理解，那么nice这个值，用过linux系统的人都知道，这是一个从unix下继承过来的概念，表示谦让度，是一个从～-的数，可以通过nice和renice指令来设置。从代码中也能看到值越小就越不会谦让他人。

       从这里我们看出FIFO和RR至少有的基数，所以在有FIFO和RR调度政策进程存在时，OTHER进程是没有机会被调度的到的。从权值计算公式同时也能看出，FIFO先来先服务的调度政策满足了，但RR这个时间片轮流的调度如果按照这种权值计算是不能满足时间片轮流这一概念的。这里只是权值的计算，在调度时候对RR政策的进程特殊处理。

       以上都是权值计算，下面看看真正的调度过程，首先是对RR政策进程的特殊处理，如果当前进程采用的RR政策，那么看他的时间片是否用完，用完了就踢到就绪队列尾部，同时恢复他的时间片。然后是便利整个就绪队列，找到第一个权值最大的进程来运行。

       整体调度效果就是：如果有FIFO和RR政策的进程，就优先调度他们2个，他们之间看已执行时间长短决定胜负，而2种政策内部则遵守各自调度政策。而OTHER只有在前面2种不存在于就绪队列时候才有可能执行，他们实际也是轮流执行，但他们之间是靠剩余时间和NICE值来决定胜负。同时就绪队列中排在最前面的最优先考虑在同样权值情况下。

从Linux内核源码的角度深入解释进程（图例解析）

       进程，作为操作系统的基本概念，是程序执行过程的体现，自计算机诞生以来，其工作原理沿用冯诺依曼架构。从代码编译生成的可执行文件在特定环境中加载到内存，便构成了一个执行中的进程。进程的生命周期涉及启动、状态转换、执行和退出等阶段。在Linux中，进程的创建始于fork调用，通过复制当前进程生成新进程，接着通过exec初始化新进程地址空间，进入就绪状态等待调度。

       进程在操作系统中被抽象为task_struct，这个庞大的结构体，即进程描述符，记录了进程的全部属性和操作，包括进程ID(pid)和状态。查看进程ID和父进程ID可以通过特定命令。状态字段通过long类型表示，dy评论采集源码其他细节可以通过源码深入探究。

       创建进程涉及fork和copy_process函数，fork仅复制轻量级信息，使用写时复制技术避免数据冲突。fork后的子进程在必要时通过exec开始独立执行。在Linux中，线程和进程本质上是相同的，区别在于资源的共享程度。

       进程调度采用抢占式策略，如CFS（完全公平调度）通过虚拟运行时来实现公平调度，通过时间记账和红黑树组织队列来高效选择进程。进程退出时，会清理资源并可能转化为孤儿进程，由特定进程接管。理解这些原理有助于深入理解Linux内核对进程的管理机制。

Linux 调度器BFS 实现原理

       调度器是操作系统的核心组件，其设计复杂且技术含量高。在众多调度器中，BFS因其简单的实现原理而备受关注。本文旨在深入探讨BFS调度器的实现机制及其关键概念，以帮助读者对Linux调度器有更直观的理解。

       首先，了解几个关键概念至关重要。虚拟Deadline（Virtual Deadline）是进程被赋予的一个固定时间片和虚拟截止日期，计算公式为：Virtual Deadline = jiffies + (user_priority * rr_interval)。其中，jiffies表示当前时间，user_priority为进程优先级，rr_interval近似为进程必须被调度的最后期限。虚拟Deadline虽表达了愿望，但并非刚性约束，其目的是为了调度决策提供依据。

       在操作系统内部，所有Ready进程被存储在进程队列中，调度器从队列中选取下一个执行的进程。BFS采用传统的bitmap加队列表示方法来管理进程队列，将所有进程分为四类，分别对应不同的调度策略：实时进程、交互式任务、普通进程及低优先级任务。

       BFS将实时进程划分为个不同优先级，采用Round Robin或FIFO方法调度同一优先级的实时进程。交互式任务需要超级用户权限，旨在服务对延迟敏感但占用CPU时间不多的任务。普通进程采用主流调度器CFS中的SCHED_OTHER策略，实现基本的分时调度。低优先级任务类同于CFS中的SCHED_IDLE策略，即CPU即将空闲时才被调度。

       每个策略下，系统中可能同时存在多个进程处于Ready状态。为此，BFS使用个bitmap来表示每个类型进程的就绪情况，当任一类型队列非空时，相应的bitmap位被置为1。

       调度器在复杂结构中选择下一个被调度进程的机制被称为“Task Selection”或“pick next”。其选择原则如下：首先检查bitmap是否有置位位，优先处理SCHED_ISO或RT task。随后，遍历对应子队列，采用EEVDF算法选择虚拟截止日期最小的进程。对于RT进程，直接选择队列首进程；对于其他队列，则通过遍历双向列表比较虚拟截止日期。若某个进程的虚拟截止日期小于当前jiffies，BFS会立即调度该进程，确保进程不会出现饥饿现象。

       调度器面临三个基本场景：进程唤醒、进程睡眠及时间片用尽。当进程唤醒时，调度器执行任务插入操作，将进程插入队列。在插入之前，BFS会比较新进程与当前运行进程的虚拟截止日期，以实现快速抢占。进程主动睡眠时，期货数据源码调度器将其从队列中移除，但虚拟截止日期保持不变，以加速进程唤醒后的调度。当进程用完时间片，调度器会剥夺CPU时间，根据公式重新计算虚拟截止日期，确保进程不会饥饿。

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=)个链表中，每一个链表代表一个优先级，系统中支持多少个优先级就有多少个链表。每次调度，调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率，复杂度为O(1);

       在linux 2.6近期的版本中，可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度，调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

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

       这是因为，与此同时，调度程序对公平性的实现从上面提到的第一种思路改变为第二种思路(通过动态调整优先级实现)。而O(1)的算法是基于一组数目不大的链表来实现的，按我的理解，这使得优先级的取值范围很小(区分度很低)，不能满足公平性的需求。而使用红黑树则对优先级的取值没有限制(可以用位、位、或更多位来表示优先级的值)，并且O(logN)的复杂度也还是很高效的。

       调度触发的时机

       调度的触发主要有如下几种情况：

       1、当前进程(正在CPU上运行的进程)状态变为非可执行状态。

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

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

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

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

       优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒，或因为释放互斥对象(如释放锁)而被唤醒;

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

       内核在响应中断的过程中，发现优先级更高的进程所等待的外部资源的变为可用，从而将其唤醒。比如CPU收到网卡中断，内核处理该中断，发现某个socket可读，于是唤醒正在等待读这个socket的进程;再比如内核在处理时钟中断的过程中，触发了定时器，从而唤醒对应的正在nanosleep系统调用中睡眠的进程。

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

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

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

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

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

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

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

       所有任务都采用FIFO时：

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

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

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

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

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

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

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

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

       3，调度程序遍历就绪队列，根据实时优先级计算调度权值(+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)，这种模式使能了所有实时功能，因此完全能够满足软实时需求，它适用于延迟要求为微秒或稍低的实时系统。

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

linux进程相关三：进程调度算法

       进程在Linux系统中主要分为CPU消耗型和IO消耗型。CPU消耗型进程在执行指令时占用大量CPU资源，而IO消耗型进程则在等待IO操作完成时消耗时间。对于IO消耗型进程，CPU性能的好坏相对不那么重要，关键在于能否及时调度到CPU，以避免整体耗时呈线性增长。因此，一般情况下，IO消耗型进程的调度优先级会高于CPU消耗型进程。

       在手机等操作系统的硬件配置上，通常会提供4个高性能核心和4个性能较低的核心。高性能核心用于服务CPU密集型任务，而性能较低的核心则专门用于处理IO消耗型任务。这样，系统实际上只需要使用4个高性能核心加上4个性能较低的核心，却能够提供相当于8核心的性能。

       在系统设计中，吞吐量和响应时间是一个需要平衡的考虑因素。吞吐量关注的是整个系统能够处理的负载量，即在特定时间单位内最大化处理工作负载的能力。而响应时间则关注的是最小化某个任务的响应时间，可能会牺牲其他任务的执行。在某些实时操作系统中，高优先级任务一旦准备好就会抢占低优先级任务，这会降低吞吐量，因为操作系统花费时间在任务切换而不是执行任务上。上下文切换不仅要考虑切换的时间，还要考虑缓存丢失的影响，即从执行一个任务切换到另一个任务时，系统可能需要重新加载内存中的数据，导致性能下降。

       Linux调度算法从2.6版本开始，通过引入优先级和不同的调度策略来实现对任务的管理。初始版本中，Linux内核空间的进程优先级被划分到0-之间，其中0-为实时（RT）策略，-为非实时策略。对于0-的RT策略，系统在所有进程进入睡眠状态时会调度非RT进程，而进程的优先级主要通过nice值来调整。nice值越低，优先级越高，这旨在奖励那些倾向于等待而非计算的进程，以提高IO消耗型进程的调度优先级。然而，这种模式在后续版本中被两个改进策略所取代：RT门限和CFS公平调度算法。

       RT门限策略限制了实时进程在特定周期内的执行时间，以避免它们长时间占用资源。CFS（Completely Fair Scheduler）公平调度算法则为普通进程提供了一种完全公平的调度方式。CFS算法使用红黑树数据结构来管理进程的运行时间，优先调度那些虚拟运行时间最短的进程。这种算法考虑了nice值较低的IO消耗型进程的需求，确保它们能够得到及时的调度。

       通过调整进程的nice值、使用renice或chrt命令，Linux系统允许用户改变进程的优先级。nice值较低的进程通常更有可能被调度，以优化系统资源的利用，特别是对于那些需要及时响应或IO密集型的任务。