linux内核调度

Ⅰ 一文读懂linux任务间调度原理和整个执行过程

在前文中，我们分析了内核中进程和线程的统一结构体task_struct，并分析进程、线程的创建和派生的过程。在本文中，我们会对任务间调度进行详细剖析，了解其原理和整个执行过程。由此，进程、线程部分的大体框架就算是介绍完了。本节主要分为三个部分：Linux内核中常见的调度策略，调度的基本结构体以及调度发生的整个流程。下面将详细展开说明。

Linux 作为一个多任务操作系统，将每个 CPU 的时间划分为很短的时间片，再通过调度器轮流分配给各个任务使用，因此造成多任务同时运行的错觉。为了维护 CPU 时间，Linux 通过事先定义的节拍率（内核中表示为 HZ），触发时间中断，并使用全局变量 Jiffies 记录了开机以来的节拍数。每发生一次时间中断，Jiffies 的值就加 1。节拍率 HZ 是内核的可配选项，可以设置为 100、250、1000 等。不同的系统可能设置不同的数值，可以通过查询 /boot/config 内核选项来查看它的配置值。

Linux的调度策略主要分为实时任务和普通任务。实时任务需求尽快返回结果，而普通任务则没有较高的要求。在前文中我们提到了task_struct中调度策略相应的变量为policy，调度优先级有prio, static_prio, normal_prio, rt_priority几个。优先级其实就是一个数值，对于实时进程来说，优先级的范围是 0 99；对于普通进程，优先级的范围是 100 139。数值越小，优先级越高。

实时调度策略主要包括以下几种

普通调度策略主要包括以下几种：

首先，我们需要一个结构体去执行调度策略，即sched_class。该类有几种实现方式

普通任务调度实体源码如下，这里面包含了 vruntime 和权重 load_weight，以及对于运行时间的统计。

在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序的红黑树结构组合起来，vruntime 最小的在树的左侧，vruntime最多的在树的右侧。以CFS策略为例，则会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。而这颗红黑树，我们称之为运行时队列（run queue），即struct rq。

其中包含结构体cfs_rq，其定义如下，主要是CFS调度相关的结构体，主要有权值相关变量、vruntime相关变量以及红黑树指针，其中结构体rb_root_cached即为红黑树的节点

对结构体dl_rq有类似的定义，运行队列由红黑树结构体构成，并按照deadline策略进行管理

对于实施队列相应的rt_rq则有所不同，并没有用红黑树实现。

下面再看看调度类sched_class，该类以函数指针的形式定义了诸多队列操作，如

调度类分为下面几种：

队列操作中函数指针指向不同策略队列的实际执行函数函数，在linux/kernel/sched/目录下，fair.c、idle.c、rt.c等文件对不同类型的策略实现了不同的函数，如fair.c中定义了

以选择下一个任务为例，CFS对应的是pick_next_task_fair，而rt_rq对应的则是pick_next_task_rt，等等。

由此，我们来总结一下：

有了上述的基本策略和基本调度结构体，我们可以形成大致的骨架，下面就是需要核心的调度流程将其拼凑成一个整体，实现调度系统。调度分为两种，主动调度和抢占式调度。

说到调用，逃不过核心函数schele()。其中sched_submit_work()函数完成当前任务的收尾工作，以避免出现如死锁或者IO中断等情况。之后首先禁止抢占式调度的发生，然后调用__schele()函数完成调度，之后重新打开抢占式调度，如果需要重新调度则会一直重复该过程，否则结束函数。

而__schele()函数则是实际的核心调度函数，该函数主要操作包括选取下一进程和进行上下文切换，而上下文切换又包括用户态空间切换和内核态的切换。具体的解释可以参照英文源码注释以及中文对各个步骤的注释。

其中核心函数是获取下一个任务的pick_next_task()以及上下文切换的context_switch()，下面详细展开剖析。首先看看pick_next_task()，该函数会根据调度策略分类，调用该类对应的调度函数选择下一个任务实体。根据前文分析我们知道，最终是在不同的红黑树上选择最左节点作为下一个任务实体并返回。

下面来看看上下文切换。上下文切换主要干两件事情，一是切换任务空间，也即虚拟内存；二是切换寄存器和 CPU 上下文。关于任务空间的切换放在内存部分的文章中详细介绍，这里先按下不表，通过任务空间切换实际完成了用户态的上下文切换工作。下面我们重点看一下内核态切换，即寄存器和CPU上下文的切换。

switch_to()就是寄存器和栈的切换，它调用到了 __switch_to_asm。这是一段汇编代码，主要用于栈的切换， 其中32位使用esp作为栈顶指针，64位使用rsp，其他部分代码一致。通过该段汇编代码我们完成了栈顶指针的切换，并调用__switch_to完成最终TSS的切换。注意switch_to中其实是有三个变量，分别是prev, next, last，而实际在使用时，我们会对last也赋值为prev。这里的设计意图需要结合一个例子来说明。假设有ABC三个任务，从A调度到B，B到C，最后C回到A，我们假设仅保存prev和next，则流程如下

最终调用__switch_to()函数。该函数中涉及到一个结构体TSS(Task State Segment)，该结构体存放了所有的寄存器。另外还有一个特殊的寄存器TR（Task Register）会指向TSS，我们通过更改TR的值，会触发硬件保存CPU所有寄存器在当前TSS，并从新的TSS读取寄存器的值加载入CPU，从而完成一次硬中断带来的上下文切换工作。系统初始化的时候，会调用 cpu_init()给每一个 CPU 关联一个 TSS，然后将 TR 指向这个 TSS，然后在操作系统的运行过程中，TR 就不切换了，永远指向这个 TSS。当修改TR的值得时候，则为任务调度。

更多Linux内核视频教程文本资料免费领取后台私信【 内核大礼包 】自行获取。

在完成了switch_to()的内核态切换后，还有一个重要的函数finish_task_switch()负责善后清理工作。在前面介绍switch_to三个参数的时候我们已经说明了使用last的重要性。而这里为何让prev和last均赋值为prev，是因为prev在后面没有需要用到，所以节省了一个指针空间来存储last。

至此，我们完成了内核态的切换工作，也完成了整个主动调度的过程。

抢占式调度通常发生在两种情况下。一种是某任务执行时间过长，另一种是当某任务被唤醒的时候。首先看看任务执行时间过长的情况。

该情况需要衡量一个任务的执行时间长短，执行时间过长则发起抢占。在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统时间又过去一个时钟周期，通过这种方式可以查看是否是需要抢占的时间点。

时钟中断处理函数会调用scheler_tick()。该函数首先取出当前CPU，并由此获取对应的运行队列rq和当前任务curr。接着调用该任务的调度类sched_class对应的task_tick()函数进行时间事件处理。

以普通任务队列为例，对应的调度类为fair_sched_class，对应的时钟处理函数为task_tick_fair()，该函数会获取当前的调度实体和运行队列，并调用entity_tick()函数更新时间。

在entity_tick()中，首先会调用update_curr()更新当前任务的vruntime，然后调用check_preempt_tick()检测现在是否可以发起抢占。

check_preempt_tick() 先是调用 sched_slice() 函数计算出一个调度周期中该任务运行的实际时间 ideal_runtime。sum_exec_runtime 指任务总共执行的实际时间，prev_sum_exec_runtime 指上次该进程被调度时已经占用的实际时间，所以 sum_exec_runtime - prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了。除了这个条件之外，还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了。

如果确认需要被抢占，则会调用resched_curr()函数，该函数会调用set_tsk_need_resched()标记该任务为_TIF_NEED_RESCHED，即该任务应该被抢占。

某些任务会因为中断而唤醒，如当 I/O 到来的时候，I/O进程往往会被唤醒。在这种时候，如果被唤醒的任务优先级高于 CPU 上的当前任务，就会触发抢占。try_to_wake_up() 调用 ttwu_queue() 将这个唤醒的任务添加到队列当中。ttwu_queue() 再调用 ttwu_do_activate() 激活这个任务。ttwu_do_activate() 调用 ttwu_do_wakeup()。这里面调用了 check_preempt_curr() 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。

由前面的分析，我们知道了不论是是当前任务执行时间过长还是新任务唤醒，我们均会对现在的任务标记位_TIF_NEED_RESCUED，下面分析实际抢占的发生。真正的抢占还需要一个特定的时机让正在运行中的进程有机会调用一下 __schele()函数，发起真正的调度。

实际上会调用__schele()函数共有以下几个时机

从系统调用返回用户态：以64位为例，系统调用的链路为do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop。在exit_to_usermode_loop中，会检测是否为_TIF_NEED_RESCHED，如果是则调用__schele()

内核态启动：内核态的执行中，被抢占的时机一般发生在 preempt_enable() 中。在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。preempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schele->preempt_schele_common->__schele 进行调度。

   本文分析了任务调度的策略、结构体以及整个调度流程，其中关于内存上下文切换的部分尚未详细叙述，留待内存部分展开剖析。

1、调度相关结构体及函数实现

2、schele核心函数

Ⅱ 如何将linux内核的CFS调度算法修改为随机调

1、实时调度优先于CFS。 2、CFS是按照各进程静态优先级的比例进行时间的分配，在一个周期内各进程都有运行机会；实时调度总是调度实时优先级最高的进程运行，运行时间和机会上都不公平。

Ⅲ linux操作系统的组成有哪几部分

Linux操作系统是当前非常火的服务端系统，所有的it方向的大学生，都应该好好掌握它。

Ⅳ 为什么说LINUX 内核调度的是线程，而不是进程呢 难道内核中进程是不切换，只切换线程

貌似不对哦，在LINUX系统之中，被调度的应该是进程。因为只有进程才拥有一个独立的上下文环境，是分配系统资源的最小单位……而线程在SMP体系中加速了执行的效率……
在LINUX之中，线程也可称作轻量级进程，它能享有自己的堆栈，线程ID等独立资源，但大多还是要依赖其创建进程，比如地址空间，信号，文件句柄……

Ⅳ linux内核同一个优先级的任务怎么调度的

1. Linux内核中用task指代一切进程和线程。

2. 调度的作用是安排所有可以运行的进程在CPU上的运行时间和次序

3. 内核中主要有两类调度算法。其中的实时调度算法中，对task有优先级的概念，同一优先级内的进程可以按照FIFO或RoundRobin的算法进行调度。这两种算法都需要维护一个可运行进程的队列。

Ⅵ linux内核同步问题

Linux内核设计与实现 十、内核同步方法

手把手教Linux驱动5-自旋锁、信号量、互斥体概述

== 基础概念： ==

并发 ：多个执行单元同时进行或多个执行单元微观串行执行，宏观并行执行

竞态 ：并发的执行单元对共享资源（硬件资源和软件上的全局变量）的访问而导致的竟态状态。

临界资源 ：多个进程访问的资源

临界区 ：多个进程访问的代码段

== 并发场合： ==

1、单CPU之间进程间的并发 :时间片轮转，调度进程。 A进程访问打印机，时间片用完，OS调度B进程访问打印机。

2、单cpu上进程和中断之间并发 ：CPU必须停止当前进程的执行中断;

3、多cpu之间

4、单CPU上中断之间的并发

== 使用偏向： ==

==信号量用于进程之间的同步，进程在信号量保护的临界区代码里面是可以睡眠的（需要进行进程调度），这是与自旋锁最大的区别。==

信号量又称为信号灯，它是用来协调不同进程间的数据对象的，而最主要的应用是共享内存方式的进程间通信。本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。它负责协调各个进程，以保证他们能够正确、合理的使用公共资源。它和spin lock最大的不同之处就是：无法获取信号量的进程可以睡眠，因此会导致系统调度。

1、==用于进程与进程之间的同步==

2、==允许多个进程进入临界区代码执行，临界区代码允许睡眠；==

3、信号量本质是==基于调度器的==，在UP和SMP下没有区别；进程获取不到信号量将陷入休眠，并让出CPU；

4、不支持进程和中断之间的同步

5、==进程调度也是会消耗系统资源的，如果一个int型共享变量就需要使用信号量，将极大的浪费系统资源==

6、信号量可以用于多个线程，用于资源的计数（有多种状态）

==信号量加锁以及解锁过程：==

sema_init(&sp->dead_sem, 0); / 初始化 /

down(&sema);

临界区代码

up(&sema);

==信号量定义：==

==信号量初始化：==

==dowm函数实现：==

==up函数实现：==

信号量一般可以用来标记可用资源的个数。

举2个生活中的例子：

==dowm函数实现原理解析：==

（1）down

判断sem->count是否 > 0，大于0则说明系统资源够用，分配一个给该进程，否则进入__down(sem);

（2）__down

调用__down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);其中TASK_UNINTERRUPTIBLE=2代表进入睡眠，且不可以打断；MAX_SCHEDULE_TIMEOUT休眠最长LONG_MAX时间；

（3）list_add_tail(&waiter.list, &sem->wait_list);

把当前进程加入到sem->wait_list中；

（3）先解锁后加锁;

进入__down_common前已经加锁了，先把解锁，调用schele_timeout(timeout)，当waiter.up=1后跳出for循环；退出函数之前再加锁；

Linux内核ARM构架中原子变量的底层实现研究

rk3288 原子操作和原子位操作

原子变量适用于只共享一个int型变量；

1、原子操作是指不被打断的操作，即它是最小的执行单位。

2、最简单的原子操作就是一条条的汇编指令(不包括一些伪指令，伪指令会被汇编器解释成多条汇编指令)

==常见函数：==

==以atomic_inc为例介绍实现过程==

在Linux内核文件archarmincludeasmatomic.h中。 执行atomic_read、atomic_set这些操作都只需要一条汇编指令，所以它们本身就是不可打断的。 需要特别研究的是atomic_inc、atomic_dec这类读出、修改、写回的函数。

所以atomic_add的原型是下面这个宏：

atomic_add等效于：

result（%0） tmp（%1） (v->counter)（%2） (&v->counter)（%3） i（%4）

注意：根据内联汇编的语法，result、tmp、&v->counter对应的数据都放在了寄存器中操作。如果出现上下文切换，切换机制会做寄存器上下文保护。

（1）ldrex %0, [%3]

意思是将&v->counter指向的数据放入result中，并且（分别在Local monitor和Global monitor中）设置独占标志。

（2）add %0, %0, %4

result = result + i

（3）strex %1, %0, [%3]

意思是将result保存到&v->counter指向的内存中， 此时 Exclusive monitors会发挥作用，将保存是否成功的标志放入tmp中。

（4） teq %1, #0

测试strex是否成功（tmp == 0 ？？）

（5）bne 1b

如果发现strex失败，从（1）再次执行。

Spinlock 是内核中提供的一种比较常见的锁机制，==自旋锁是“原地等待”的方式解决资源冲突的==，即，一个线程获取了一个自旋锁后，另外一个线程期望获取该自旋锁，获取不到，只能够原地“打转”（忙等待）。由于自旋锁的这个忙等待的特性，注定了它使用场景上的限制 —— 自旋锁不应该被长时间的持有（消耗 CPU 资源），一般应用在==中断上下文==。

1、spinlock是一种死等机制

2、信号量可以允许多个执行单元进入，spinlock不行，一次只能允许一个执行单元获取锁，并且进入临界区，其他执行单元都是在门口不断的死等

3、由于不休眠，因此spinlock可以应用在中断上下文中；

4、由于spinlock死等的特性，因此临界区执行代码尽可能的短；

==spinlock加锁以及解锁过程：==

spin_lock(&devices_lock);

临界区代码

spin_unlock(&devices_lock);

==spinlock初始化==

==进程和进程之间同步==

==本地软中断之间同步==

==本地硬中断之间同步==

==本地硬中断之间同步并且保存本地中断状态==

==尝试获取锁==

== arch_spinlock_t结构体定义如下： ==

== arch_spin_lock的实现如下： ==

lockval（%0） newval（%1） tmp（%2） &lock->slock（%3） 1 << TICKET_SHIFT（%4）

（1）ldrex %0, [%3]

把lock->slock的值赋值给lockval；并且（分别在Local monitor和Global monitor中）设置独占标志。

（2）add %1, %0, %4

newval =lockval +（1<<16）; 相当于next+1；

（3）strex %2, %1, [%3]

newval =lockval +（1<<16）; 相当于next+1；

意思是将newval保存到 &lock->slock指向的内存中， 此时 Exclusive monitors会发挥作用，将保存是否成功的标志放入tmp中。

（4） teq %2, #0

测试strex是否成功

（5）bne 1b

如果发现strex失败，从（1）再次执行。

通过上面的分析，可知关键在于strex的操作是否成功的判断上。而这个就归功于ARM的Exclusive monitors和ldrex/strex指令的机制。

（6）while (lockval.tickets.next != lockval.tickets.owner)

如何lockval.tickets的next和owner是否相等。相同则跳出while循环，否则在循环内等待判断；

* （7）wfe()和smp_mb() 最终调用#define barrier() asm volatile ("": : :"memory") *

阻止编译器重排，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。

== arch_spin_unlock的实现如下： ==

退出锁时：tickets.owner++

== 出现死锁的情况： ==

1、拥有自旋锁的进程A在内核态阻塞了，内核调度B进程，碰巧B进程也要获得自旋锁，此时B只能自旋转。 而此时抢占已经关闭，（单核）不会调度A进程了，B永远自旋，产生死锁。

2、进程A拥有自旋锁，中断到来，CPU执行中断函数，中断处理函数，中断处理函数需要获得自旋锁，访问共享资源，此时无法获得锁，只能自旋，产生死锁。

== 如何避免死锁： ==

1、如果中断处理函数中也要获得自旋锁，那么驱动程序需要在拥有自旋锁时禁止中断；

2、自旋锁必须在可能的最短时间内拥有

3、避免某个获得锁的函数调用其他同样试图获取这个锁的函数，否则代码就会死锁；不论是信号量还是自旋锁，都不允许锁拥有者第二次获得这个锁，如果试图这么做，系统将挂起；

4、锁的顺序规则（a) 按同样的顺序获得锁；b) 如果必须获得一个局部锁和一个属于内核更中心位置的锁，则应该首先获取自己的局部锁 ;c) 如果我们拥有信号量和自旋锁的组合，则必须首先获得信号量；在拥有自旋锁时调用down(可导致休眠)是个严重的错误的；）

== rw（read/write）spinlock： ==

加锁逻辑：

1、假设临界区内没有任何的thread，这个时候任何的读线程和写线程都可以键入

2、假设临界区内有一个读线程，这时候信赖的read线程可以任意进入，但是写线程不能进入；

3、假设临界区有一个写线程，这时候任何的读、写线程都不可以进入；

4、假设临界区内有一个或者多个读线程，写线程不可以进入临界区，但是写线程也无法阻止后续的读线程继续进去，要等到临界区所有的读线程都结束了，才可以进入，可见：==rw（read/write）spinlock更加有利于读线程；==

== seqlock（顺序锁）： ==

加锁逻辑：

1、假设临界区内没有任何的thread，这个时候任何的读线程和写线程都可以键入

2、假设临界区内没有写线程的情况下，read线程可以任意进入；

3、假设临界区有一个写线程，这时候任何的读、写线程都不可以进入；

4、假设临界区内只有read线程的情况下，写线程可以理解执行，不会等待，可见：==seqlock（顺序锁）更加有利于写线程；==

读写速度 ： CPU > 一级缓存 > 二级缓存 > 内存 ，因此某一个CPU0的lock修改了，其他的CPU的lock就会失效；那么其他CPU就会依次去L1 L2和主存中读取lock值，一旦其他CPU去读取了主存，就存在系统性能降低的风险；

mutex用于互斥操作。

互斥体只能用于一个线程，资源只有两种状态（占用或者空闲）

1、mutex的语义相对于信号量要简单轻便一些，在锁争用激烈的测试场景下，mutex比信号量执行速度更快，可扩展

性更好，

2、另外mutex数据结构的定义比信号量小;、

3、同一时刻只有一个线程可以持有mutex

4、不允许递归地加锁和解锁

5、当进程持有mutex时，进程不可以退出。

• mutex必须使用官方API来初始化。

• mutex可以睡眠，所以不允许在中断处理程序或者中断下半部中使用，例如tasklet、定时器等

==常见操作：==

struct mutex mutex_1;

mutex_init(&mutex_1);

mutex_lock(&mutex_1)

临界区代码；

mutex_unlock(&mutex_1)

==常见函数：==

=

Ⅶ 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中常见IO调度器

对于磁盘I/O，Linux提供了cfq, deadline和noop三种调度策略

考虑到硬件配置、实际应用场景（读写比例、顺序还是随机读写）的差异，上面的简单解释对于实际选择没有太大帮助，实际该选择哪个基本还是要实测来验证。不过下面几条说明供参考：

NOOP全称No Operation,中文名称电梯式调度器，该算法实现了最简单的FIFO队列，所有I/O请求大致按照先来后到的顺序进行操作。NOOP实现了一个简单的FIFO队列,它像电梯的工作方式一样对I/O请求进行组织。它是基于先入先出（FIFO）队列概念的 Linux 内核里最简单的I/O 调度器。此调度程序最适合于固态硬盘。

Deadline翻译成中文是截止时间调度器，是对Linus Elevator的一种改进，它避免有些请求太长时间不能被处理。另外可以区分对待读操作和写操作。DEADLINE额外分别为读I/O和写I/O提供了FIFO队列。

Deadline对读写request进行了分类管理，并且在调度处理的过程中读请求具有较高优先级。这主要是因为读请求往往是同步操作，对延迟时间比较敏感，而写操作往往是异步操作，可以尽可能的将相邻访问地址的请求进行合并，但是，合并的效率越高，延迟时间会越长。因此，为了区别对待读写请求类型，deadline采用两条链表对读写请求进行分类管理。但是，引入分类管理之后，在读优先的情况下，写请求如果长时间得到不到调度，会出现饿死的情况，因此，deadline算法考虑了写饿死的情况，从而保证在读优先调度的情况下，写请求不会被饿死。

总体来讲，deadline算法对request进行了优先权控制调度，主要表现在如下几个方面：

CFQ全称Completely Fair Scheler ，中文名称完全公平调度器，它是现在许多 Linux 发行版的默认调度器，CFQ是内核默认选择的I/O调度器。它将由进程提交的同步请求放到多个进程队列中，然后为每个队列分配时间片以访问磁盘。 对于通用的服务器是最好的选择，CFQ均匀地分布对I/O带宽的访问 。CFQ为每个进程和线程，单独创建一个队列来管理该进程所产生的请求,以此来保证每个进程都能被很好的分配到I/O带宽，I/O调度器每次执行一个进程的4次请求。该算法的特点是按照I/O请求的地址进行排序，而不是按照先来后到的顺序来进行响应。简单来说就是给所有同步进程分配时间片，然后才排队访问磁盘。

多队列无操作I / O调度程序。不对请求进行重新排序，最小的开销。NVME等快速随机I / O设备的理想选择。

这是对最后期限I / O调度程序的改编，但设计用于 多队列设备。一个出色的多面手，CPU开销相当低。