linux进程调度的队列

‘壹’ linux环境下的进程调度算法有哪些

第一部分： 实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheling-SD）、以及基于时间的进程调度算法（Time-driven scheling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：

这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。

动态优先级调度算法：

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

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

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

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER 调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少； counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给 counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中， priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；

SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；

当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；

Linux内核实现中使用了大量的封中断操作会造成中断的丢失；

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

虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：

图 1 RT-Linux结构

RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时， RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

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

RT -Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。

3.2. Kurt-Linux

Kurt -Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；

Start-Time：作业的开始时间；

Finish-Time：作业的结束时间；

Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

‘贰’ linux 内核中关于进程调度的内容在哪个目录下schele函数在哪里

linux进程调度中最基本的数据结构是struct runqueue；有关于此结构的队列在kernel/sched.c，此队列包含了处理器的所有可执行进程的信息。
每个运行队列都有两个优先级数组，一个活跃的和一个过期的，此数组也是在kernel/sched.c中含有。
schele函数定义也是在kernel/sched.c中。

‘叁’ linux 内核中，工作队列和线程有什么区别

一句话概括：根本就是两个不同的概念，差别很大。
简单的说：
一般来说，线程是windows上的概念，windows区分进程和线程。而在linux上，统一叫进程，进程是完成某项任务所需资源的集合，同时也是linux基本的执行单元。
工作队列是一个等待被执行的任务链表，由专有的线程来调度、执行。很多linux驱动的中断下半部的实现，都是采用工作队列的方式。

作者：陈彬
链接：
来源：知乎
着作权归作者所有，转载请联系作者获得授权。

‘肆’ linux进程调度的三种策略是什么

linux内核的三种主要调度策略：
1，SCHED_OTHER 分时调度策略，
2，SCHED_FIFO实时调度策略，先到先服务
3，SCHED_RR实时调度策略，时间片轮转

实时进程将得到优先调用，实时进程根据实时优先级决定调度权值。分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。

SHCED_RR和SCHED_FIFO的不同：
当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。
SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。
如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。

相同点：
RR和FIFO都只用于实时任务。
创建时优先级大于0(1-99)。
按照可抢占优先级调度算法进行。
就绪态的实时任务立即抢占非实时任务。

所有任务都采用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微秒或稍低的实时系统。
实现实时是以牺牲系统的吞吐率为代价的，因此实时性越好，系统吞吐率就越低。

‘伍’ linux内核怎么调度系统

1.调度器的概述

多任务操作系统分为非抢占式多任务和抢占式多任务。与大多数现代操作系统一样，Linux采用的是抢占式多任务模式。这表示对CPU的占用时间由操作系统决定的，具体为操作系统中的调度器。调度器决定了什么时候停止一个进程以便让其他进程有机会运行，同时挑选出一个其他的进程开始运行。

2.调度策略

在Linux上调度策略决定了调度器是如何选择一个新进程的时间。调度策略与进程的类型有关，内核现有的调度策略如下：

#define SCHED_NORMAL 0#define SCHED_FIFO 1#define SCHED_RR 2#define SCHED_BATCH 3/* SCHED_ISO: reserved but not implemented yet */#define SCHED_IDLE 5

0: 默认的调度策略，针对的是普通进程。
1：针对实时进程的先进先出调度。适合对时间性要求比较高但每次运行时间比较短的进程。
2：针对的是实时进程的时间片轮转调度。适合每次运行时间比较长得进程。
3：针对批处理进程的调度，适合那些非交互性且对cpu使用密集的进程。
SCHED_ISO：是内核的一个预留字段，目前还没有使用
5：适用于优先级较低的后台进程。
注：每个进程的调度策略保存在进程描述符task_struct中的policy字段

3.调度器中的机制

内核引入调度类（struct sched_class）说明了调度器应该具有哪些功能。内核中每种调度策略都有该调度类的一个实例。（比如：基于公平调度类为：fair_sched_class，基于实时进程的调度类实例为：rt_sched_class），该实例也是针对每种调度策略的具体实现。调度类封装了不同调度策略的具体实现，屏蔽了各种调度策略的细节实现。
调度器核心函数schele()只需要调用调度类中的接口，完成进程的调度，完全不需要考虑调度策略的具体实现。调度类连接了调度函数和具体的调度策略。

• 武特师兄关于sche_class和sche_entity的解释，一语中的。

• 调度类就是代表的各种调度策略，调度实体就是调度单位，这个实体通常是一个进程，但是自从引入了cgroup后，这个调度实体可能就不是一个进程了，而是一个组

4.schele()函数

linux 支持两种类型的进程调度，实时进程和普通进程。实时进程采用SCHED_FIFO 和SCHED_RR调度策略，普通进程采用SCHED_NORMAL策略。
preempt_disable()：禁止内核抢占
cpu_rq（）：获取当前cpu对应的就绪队列。
prev = rq->curr;获取当前进程的描述符prev
switch_count = &prev->nivcsw;获取当前进程的切换次数。
update_rq_clock() ：更新就绪队列上的时钟
clear_tsk_need_resched()清楚当前进程prev的重新调度标志。
deactive_task():将当前进程从就绪队列中删除。
put_prev_task() :将当前进程重新放入就绪队列
pick_next_task():在就绪队列中挑选下一个将被执行的进程。
context_switch():进行prev和next两个进程的切换。具体的切换代码与体系架构有关，在switch_to()中通过一段汇编代码实现。
post_schele():进行进程切换后的后期处理工作。

5.pick_next_task函数

选择下一个将要被执行的进程无疑是一个很重要的过程，我们来看一下内核中代码的实现
对以下这段代码说明：
1.当rq中的运行队列的个数(nr_running)和cfs中的nr_runing相等的时候，表示现在所有的都是普通进程，这时候就会调用cfs算法中的pick_next_task(其实是pick_next_task_fair函数)，当不相等的时候，则调用sched_class_highest(这是一个宏，指向的是实时进程)，这下面的这个for(;;)循环中，首先是会在实时进程中选取要调度的程序（p = class->pick_next_task(rq);）。如果没有选取到，会执行class=class->next;在class这个链表中有三种类型（fair,idle,rt）.也就是说会调用到下一个调度类。

• static inline struct task_struct *pick_next_task(struct rq *rq){ const struct sched_class *class; struct task_struct *p; /*


• * Optimization: we know that if all tasks are in


• * the fair class we can call that function directly:


• *///基于公平调度的普通进程


• if (likely(rq->nr_running == rq->cfs.nr_running)) {


• p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p;


• }//基于实时调度的实时进程


• class = sched_class_highest; for ( ; ; ) {


• p = class->pick_next_task(rq); //实时进程的类


• if (p) return p; /*


• * Will never be NULL as the idle class always


• * returns a non-NULL p:


• */


• class = class->next; //rt->next = fair; fair->next = idle


• }


• }



在这段代码中体现了Linux所支持的两种类型的进程，实时进程和普通进程。回顾下：实时进程可以采用SCHED_FIFO 和SCHED_RR调度策略，普通进程采用SCHED_NORMAL调度策略。
在这里首先说明一个结构体struct rq,这个结构体是调度器管理可运行状态进程的最主要的数据结构。每个cpu上都有一个可运行的就绪队列。刚才在pick_next_task函数中看到了在选择下一个将要被执行的进程时实际上用的是struct rq上的普通进程的调度或者实时进程的调度，那么具体是如何调度的呢？在实时调度中，为了实现O(1)的调度算法，内核为每个优先级维护一个运行队列和一个DECLARE_BITMAP,内核根据DECLARE_BITMAP的bit数值找出非空的最高级优先队列的编号，从而可以从非空的最高级优先队列中取出进程进行运行。
我们来看下内核的实现

• struct rt_prio_array {


• DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */


• struct list_head queue[MAX_RT_PRIO];


• };



数组queue[i]里面存放的是优先级为i的进程队列的链表头。在结构体rt_prio_array 中有一个重要的数据构DECLARE_BITMAP，它在内核中的第一如下：

• define DECLARE_BITMAP(name,bits)


• unsigned long name[BITS_TO_LONGS(bits)]



5.1对于实时进程的O(1)算法

这个数据是用来作为进程队列queue[MAX_PRIO]的索引位图。bitmap中的每一位与queue[i]对应，当queue[i]的进程队列不为空时，Bitmap的相应位就为1，否则为0，这样就只需要通过汇编指令从进程优先级由高到低的方向找到第一个为1的位置，则这个位置就是就绪队列中最高的优先级（函数sched_find_first_bit()就是用来实现该目的的）。那么queue[index]->next就是要找的候选进程。
如果还是不懂，那就来看两个图


由结果可以看出当nice的值越小的时候，其睡眠时间越短，则表示其优先级升高了。

7.关于获取和设置优先级的系统调用：sched_getscheler（）和sched_setscheler

• #include <sched.h>#include <stdlib.h>#include <stdio.h>#include <errno.h>#define DEATH(mess) { perror(mess); exit(errno); }void printpolicy (int policy){ /* SCHED_NORMAL = SCHED_OTHER in user-space */



• if (policy == SCHED_OTHER) printf ("policy = SCHED_OTHER = %d ", policy); if (policy == SCHED_FIFO) printf ("policy = SCHED_FIFO = %d ", policy); if (policy == SCHED_RR) printf ("policy = SCHED_RR = %d ", policy);


• }int main (int argc, char **argv){ int policy; struct sched_param p; /* obtain current scheling policy for this process */


• //获取进程调度的策略


• policy = sched_getscheler (0);


• printpolicy (policy); /* reset scheling policy */



• printf (" Trying sched_setscheler... ");


• policy = SCHED_FIFO;


• printpolicy (policy);


• p.sched_priority = 50; //设置优先级为50


• if (sched_setscheler (0, policy, &p))


• DEATH ("sched_setscheler:"); printf ("p.sched_priority = %d ", p.sched_priority); exit (0);


• }



输出结果：

• [root@wang schele]# ./get_schele_policy policy = SCHED_OTHER = 0



• Trying sched_setscheler...


• policy = SCHED_FIFO = 1


• p.sched_priority = 50



可以看出进程的优先级已经被改变。

‘陆’ linux内核进程调度子系统根据什么算法选择最值得运行的进程

你可以查看相关linux书籍关于这部分的介绍。
操作系统这一门课程回答了你的答案。
据我的了解，应该是多级反馈轮转调度的算法。
每个进程都是按时间片运行的。每个进程都被分配了优先级。
每个进程位于调度队列的某一级上。操作系统根据这个多级队列来调度。
每个队列按照FIFO的方式调度。
就这么多了。你可以去图书馆借书看看。

‘柒’ linux 进程调度有没有先来先服务方式

有的，先来先服务就是将来的任务按照时间先后放到队列里面，然后一个一个调度。

‘捌’ Linux内核中等待队列的几种用法

1. 睡眠等待某个条件发生(条件为假时睡眠)：
睡眠方式：wait_event, wait_event_interruptible
唤醒方式：wake_up (唤醒时要检测条件是否为真，如果还为假则继续睡眠，唤醒前一定要把条件变为真)
2. 手工休眠方式一：
1)建立并初始化一个等待队列项
DEFINE_WAIT(my_wait) <== wait_queue_t my_wait; init_wait(&my_wait);
2)将等待队列项添加到等待队列头中，并设置进程的状态
prepare_to_wait(wait_queue_head_t *queue, wait_queue_t *wait, int state)
3)调用schele()，告诉内核调度别的进程运行
4)schele返回，完成后续清理工作
finish_wait()
3. 手工休眠方式二：
1)建立并初始化一个等待队列项：
DEFINE_WAIT(my_wait) <== wait_queue_t my_wait; init_wait(&my_wait);
2)将等待队列项添加到等待队列头中：
add_wait_queue
3)设置进程状态
__set_current_status(TASK_INTERRUPTIBLE);
4)schele()
5)将等待队列项从等待队列中移除
remove_wait_queue()
其实，这种休眠方式相当于把手工休眠方式一中的第二步prepare_to_wait拆成两步做了，即prepare_to_wait <====add_wait_queue + __set_current_status，其他都是一样的。
4. 老版本的睡眠函数sleep_on(wait_queue_head_t *queue)：

‘玖’ 操作系统中进程调度策略有哪几种

linux内核的三种调度方法：

1，SCHED_OTHER 分时调度策略，

2，SCHED_FIFO实时调度策略，先到先服务

3，SCHED_RR实时调度策略，时间片轮转

实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾使用了cpu最少的进程将会得到优先调度。

SHCED_RR和SCHED_FIFO的不同：

当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾确保了任何具备相同优先级的RR任务的调度公平。

‘拾’ Linux 工作队列和等待队列的区别

work queue是一种bottom half，中断处理的后半程，强调的是动态的概念，即work是重点，而queue是其次。
wait queue是一种“任务队列”，可以把一些进程放在上面睡眠等待某个事件，强调静态多一些，重点在queue上，即它就是一个queue，这个queue如何调度，什么时候调度并不重要
等待队列在内核中有很多用途，尤其适合用于中断处理，进程同步及定时。这里只说，进程经常必须等待某些事件的发生。例如，等待一个磁盘操作的终止，等待释放系统资源，或者等待时间经过固定的间隔。
等待队列实现了在事件上的条件等待，希望等待特定事件的进程把放进合适的等待队列，并放弃控制权。因此。等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒进程。
等待队列由循环链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头，等待队列头是一个类型为wait_queue_head_t的数据结构。
等待队列链表的每个元素代表一个睡眠进程，该进程等待某一事件的发生，描述符地址存放在task字段中。然而，要唤醒等待队列中所有的进程有时并不方便。例如，如果两个或多个进程在等待互斥访问某一个要释放的资源，仅唤醒等待队列中一个才有意义。这个进程占有资源，而其他进程继续睡眠可以用DECLARE_WAIT_QUEUE_HEAD(name)宏定义一个新的等待队列，该宏静态地声明和初始化名为name的等待队列头变量。 init_waitqueue_head()函数用于初始化已动态分配的wait queue head变量等待队列可以通过DECLARE_WAITQUEUE()静态创建，也可以用init_waitqueue_head()动态创建。进程放入等待队列并设置成不可执行状态。
工作队列，workqueue，它允许内核代码来请求在将来某个时间调用一个函数。用来处理不是很紧急事件的回调方式处理方法.工作队列的作用就是把工作推后,交由一个内核线程去执行，更直接的说就是写了一个函数,而现在不想马上执行它，需要在将来某个时刻去执行，那就得用工作队列准没错。
如果需要用一个可以重新调度的实体来执行下半部处理，也应该使用工作队列。是唯一能在进程上下文运行的下半部实现的机制。这意味着在需要获得大量的内存时、在需要获取信号量时，在需要执行阻塞式的I/O操作时，都会非常有用。