概叙

进程

        进程是操作系统虚拟出来的概念，用来组织计算机中的任务。计算机的核心是CPU，它承担了所有的计算任务；而操作系统是计算机的管理者，它负责任务的调度、资源的分配和管理，统领整个计算机硬件；应用程序侧是具有某种功能的程序，程序是运行于操作系统之上的。

        进程是一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。

        进程是一种抽象的概念，从来没有统一的标准定义。进程一般由程序、数据集合和进程控制块三部分组成。程序用于描述进程要完成的功能，是控制进程执行的指令集；数据集合是程序在执行时所需要的数据和工作区；程序控制块(Program Control Block，简称PCB)，包含进程的描述信息和控制信息，是进程存在的唯一标志。

        但随着进程被赋予越来越多的任务，进程好像有了真实的生命，它从诞生就随着CPU时间执行，直到最终消失。不过，进程的生命都得到了操作系统内核的关照。就好像疲于照顾几个孩子的母亲内核必须做出决定，如何在进程间分配有限的计算资源，最终让用户获得最佳的使用体验。内核中安排进程执行的模块称为调度器（scheduler）。

进程的优先级

        调度器分配CPU时间的基本依据，就是进程的优先级。根据程序任务性质的不同，程序可以有不同的执行优先级。根据优先级特点，我们可以把进程分为两种类别。

•         
  • 实时进程（Real-Time Process）：优先级高、需要尽快被执行的进程。它们一定不能被普通进程所阻挡，例如视频播放、各种监测系统。
  • 普通进程（Normal Process）：优先级低、更长执行时间的进程。例如文本编译器、批处理一段文档、图形渲染。

        普通进程根据行为的不同，还可以被分成互动进程（interactive process）和批处理进程（batch process）。互动进程的例子有图形界面，它们可能处在长时间的等待状态，例如等待用户的输入。一旦特定事件发生，互动进程需要尽快被激活。一般来说，图形界面的反应时间是50到100毫秒。批处理进程没有与用户交互的，往往在后台被默默地执行。

        实时进程由Linux操作系统创造，普通用户只能创建普通进程。两种进程的优先级不同，实时进程的优先级永远高于普通进程。进程的优先级是一个0到139的整数。数字越小，优先级越高。其中，优先级0到99留给实时进程，100到139留给普通进程。

        在Linux中一共有139个优先级，从kernel的视角来看，范围为[1,139]，数值越小，优先级越高。其中

• [1,99]为实时优先级，对应SCHED_FIFO、SCHED_RR调度策略的实时进程；
• [100,139]为普通优先级，对应SCHED_OTHER、SCHED_BATCH、SCHED_IDLE调度策略的普通进程，其默认优先级为120。

        这里还有一个变量叫做 nice 值，范围[-20,19]。通过调整nice值可以间接调整优先级，nice值只对普通进程生效：  普通进程优先级 = 优先级 + nice

        一个普通进程的默认优先级是120。我们可以用命令nice来修改一个进程的默认优先级。例如有一个可执行程序叫app，执行命令： $nice -n -20 ./app

        命令中的-20指的是从默认优先级上减去20。通过这个命令执行app程序，内核会将app进程的默认优先级设置成100，也就是普通进程的最高优先级。命令中的-20可以被换成-20至19中任何一个整数，包括-20 和 19。默认优先级将会变成执行时的静态优先级（static priority）。调度器最终使用的优先级根据的是进程的动态优先级：

动态优先级 = 静态优先级 – Bonus + 5

        如果这个公式的计算结果小于100或大于139，将会取100到139范围内最接近计算结果的数字作为实际的动态优先级。公式中的Bonus是一个估计值，这个数字越大，代表着它可能越需要被优先执行。如果内核发现这个进程需要经常跟用户交互，将会把Bonus值设置成大于5的数字。如果进程不经常跟用户交互，内核将会把进程的Bonus设置成小于5的数。

Linux调度策略实战

调度策略
 

在Linux上有如下调度策略，可以通过 chrt 进行查询/设置：

SCHED_FIFO：高优先级，先入先出，除非主动让出CPU，否则会一直占用CPU；

SCHED_RR：高优先级，基于时间片，轮转调度；

SCHED_OTHER：普通优先级；

SCHED_BATCH：普通优先级，针对"batch"类型的任务，切换没有SCHED_OTHER频繁;

SCHED_IDLE：普通优先级，适用于以低优先级运行的后台任务

调度策略优缺点

各种资源调度策略的优缺点如下：

FCFS：优点是简单易实现，缺点是可能导致较长作业阻塞较短作业，导致系统吞吐量较低。

SJF：优点是可以提高吞吐量和平均等待时间，缺点是需要预先知道作业的执行时间，否则会导致星际穿越问题。

优先级调度：优点是可以满足实时性要求的作业，缺点是可能导致不公平。

RR：优点是可以实现公平性和响应时间短，缺点是可能导致较长作业阻塞较短作业，导致系统吞吐量较低。

多级反馈队列：优点是可以实现公平性和响应时间短，同时满足实时性要求的作业。缺点是复杂度较高。

SRTF：优点是可以提高吞吐量和平均等待时间，缺点是需要预先知道作业的执行时间，否则会导致星际穿越问题。

进程的调度策略实操

        单个CPU同一时间仅可用执行一个进程！虽然Linux系统似乎通过多任务同时运行多个进程，但当多个进程在单个CPU上同时运行时，是通过交替执行这些进程实现的。

        要快速确定下一个进程并确保公平性、响应性、可预测性和可扩展性，操作系统通常会采用调度算法。内核通过进程调度器决定哪个进程在特定的时间运行。

# 查询主进程调度策略与优先级
chrt -p $pid
 
# 查询线程调度策略与优先级
chrt -p $tid
 
# 查询进程下所有线程调度策略与优先级
chrt -ap $pid


# 修改调度策略
chrt -o -p $prio $pid    #SCHED_OTHER, $prio = 0
chrt -f -p $prio $pid    #SCHED_FIFO,  $prio = [1,99]
chrt -r -p $prio $pid    #SCHED_RR,    $prio = [1,99] 
chrt -b -p $prio $pid    #SCHED_BATCH, $prio = 0
chrt -i -p $prio $pid    #SCHED_IDLE,  $prio = 0
 
# 获取每个调度策略所支持的min/max优先级范围
chrt -m

查询优先级
查询优先级的命令有很多，top、ps、chrt等等都可以，但是不同的工具、甚至不同的命令参数，显示的优先级范围、含义不同。

top
top可以直接看到PR(优先级)、NI(nice)。

PR范围：[-100,-2]&&[0,39]，其中-100不会直接显示，而是以字符串"rt"的形式显示。PR数值越小，优先级越高。

[root@AOS ~]# top
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
19442 ros       20   0  961708  81772  35616 S   0.3  0.5   0:16.54 node
    1 root      20   0  119812   5444   3424 S   0.0  0.0   0:18.64 systemd
    2 root      20   0       0      0      0 S   0.0  0.0   0:00.07 kthreadd
    3 root      20   0       0      0      0 S   0.0  0.0   0:00.19 ksoftirqd/0
    5 root       0 -20       0      0      0 S   0.0  0.0   0:00.00 kworker/0:0H
    9 root      rt   0       0      0      0 S   0.0  0.0   0:00.03 migration/0

ps
直接输入ps不会显示优先级信息，需要加入参数。ps具有多种风格的输入参数，不同的风格，显示的优先级范围、含义也不同。

风格1，ps elf

显示的PRI与top中的PR值一致，即[-100,-2]&&[0,39]，数值越小，优先级越高；

风格2，ps -elf

显示的PRI=top.PR+60; 即[-40,58]&&[60,99]，数值越小，优先级越高；

风格3，ps -elo pid,tid,rtprio,pri,ni,cmd

————————————————
显示的PRI范围[1,139]，数值越大，优先级越高，与内核视角的最终优先级刚好相反;


[root@AOS ~]# ps elf
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
4     0 26399 26385  20   0   7028  3908 do_sel Ss+  pts/13     0:00 -bash USER=root LOGNAME=root ......
4     0 25174 24247  20   0   7032  3808 do_wai Ss   pts/11     0:00 -bash ASCEND_VECTOR_OBJ_PATH=......
0     0 16200 15963  -2   -   5088  1480 -      RN+  pts/17    70:53  \_ dd if=/dev/zero of=......
 
[root@AOS ~]# ps -elf
F S UID        PID  PPID  C PRI  NI ADDR SZ WCHAN  STIME TTY          TIME CMD
4 S root         1     0  0  80   0 -  1156 do_wai 6月07 ?       00:00:01 init
1 S root         2     0  0  80   0 -     0 kthrea 6月07 ?       00:00:00 [kthreadd]
1 I root         3     2  0  60 -20 -     0 rescue 6月07 ?       00:00:00 [rcu_gp]
1 I root         4     2  0  60 -20 -     0 rescue 6月07 ?       00:00:00 [rcu_par_gp]
 
[root@AOS ~]# ps -eLo pid,tid,rtprio,pri,ni,cmd
  PID   TID RTPRIO PRI  NI CMD
    1     1      -  19   0 init
    3     3      -  39 -20 [rcu_gp]
   12    12     99 139   - [migration/0]



chrt
chrt只能得到SCHED_FIFO、SCHED_RR实时优先级，范围[1,99]。数值越大，优先级越高。

实时优先级 = 100 - chrt优先级
[root@AOS ~]# chrt -p 27116
pid 27116's current scheduling policy: SCHED_RR
pid 27116's current scheduling priority: 10


设置优先级
对于普通进程，可以通过nice/renice调整nice值，从而影响普通进程的优先级。普通优先级 = 120 + nice；

对于实时进程，可以通过chrt直接调整优先级。实时优先级 = 100 - chrt优先级；

nice/renice
nice用于在启动时设置nice值，

$N为nice值，范围[-20,19]，数值越小，优先级越高；

$proc_cmd为可执行程序；

nice $N $proc_cmd

renice用于程序已经启动后，再重新调整nice值，

$N为nice值，范围[-20,19]，数值越小，优先级越高；

$pid为进程id；

renice $N -p $pid

renice可以对进程下的所有线程调整nice值，

$N为nice值，范围[-20,19]，数值越小，优先级越高；

$pgrp为进程组id；

renice $N -g $pgrp

chrt
$policy为策略选项，可用-f/-r，分别为SCHED_FIFO/SCHED_RR；

$priority为优先级，范围[1,99]，数值越大，优先级越高；

$pid为进程id；

chrt -$policy -p $priority $pid

调度器

详细介绍参考：Linux 调度器发展简述_linux调度器提速的作用-CSDN博客

        Linux的进程调度器是不断演进的，先后出现过三种里程碑式的调度器：

• O(n)调度器 内核版本 2.4-2.6
• O(1) 调度器 内核版本 2.6.0-2.6.22
• CFS调度器 内核版本 2.6.23-至今

        O(n)属于早期版本在pick next过程是需要遍历进程任务队列来实现，O(1)版本性能上有较大提升可以实现O(1)复杂度的pick next过程。

        CFS调度器可以说是一种O(logn)调度器，但是其算法思想相比前两种有些不同，并且设计实现上也更加轻量，一直被Linux内核沿用至今。

• O(n)调度器采用全局runqueue，导致多cpu加锁问题和cache利用率低的问题
• O(1)调度器为每个cpu设计了一个runqueue，并且采用MLFQ算法思想设置140个优先级链表和active/expire两个双指针结构
• CFS调度器采用红黑树来实现O(logn)复杂度的pick-next算法，摒弃固定时间片机制，采用调度周期内的动态时间机制
• O(1)和O(n)都在交互进程的识别算法上下了功夫，但是无法做的100%准确
• CFS另辟蹊径采用完全公平思想以及虚拟运行时间来实现进行的调度
• CFS调度器也并非银弹，在某些方面可能不如O(1)

一、调度器介绍

        在Linux内核中，用来安排进程执行的模块称为调度器（scheduler），调度器（Scheduler）是操作系统内核的关键组件之一，负责管理和协调CPU资源在多个进程间高效、公正地分配。

        调度器的主要目标是确保CPU时间片能在系统中的各个进程间合理分配，从而最大化系统资源利用率，同时也要考虑进程的响应时间和整体系统性能。        

        它可以切换进程状态（process state）。例如执行、可中断睡眠、不可中断睡眠、退出、暂停等。

        调度器是CPU中央处理器的管理员，主要负责完成做两件事情：

• 一、选择某些就绪进程来执行，
• 二是打断某些执行的进程让它们变为就绪状态。调度器分配CPU时间的基本依据就是进程的优先级。上下文 切换（context switch）：将进程在CPU中切换执行的过程，内核承担此任务，负责重建和存储被切换掉之前的CPU状态。

        Linux 调度器将进程分为三类：交互式进程、批处理进程、实时进程。

交互式进程

        此类进程有大量的人机交互，因此进程不断地处于睡眠状态，等待用户输入。典型的应用比如编辑器 vi。此类进程对系统响应时间要求比较高，否则用户会感觉系统反应迟缓。

批处理进程

        此类进程不需要人机交互，在后台运行，需要占用大量的系统资源。但是能够忍受响应延迟。比如编译器。

实时进程

        实时对调度延迟的要求最高，这些进程往往执行非常重要的操作，要求立即响应并执行。比如视频播放软件或飞机飞行控制系统，很明显这类程序不能容忍长时间的调度延迟，轻则影响电影放映效果，重则机毁人亡。

1.结构框图

        Linux内核中用来安排调度进程 (一段程序的执行过程) 执行的模块称为调度器(Scheduler)，它可以切换进程状态 (Process status) 。比如: 执行、可中断睡眠、不可中断睡眠、退出、暂停等。

        调度器是 CPU 中央处理器的管理员，主要负责完成做两件事情：

• 一、选择某些就绪进 程来执行。
• 二、是打断某些执行的进程让它们变为就绪状态。

        调度器分配CPU 时间的基本依据：进程的优先级。

        上下文 切换（context switch ）：将进程在 CPU 中切换执行的过程，内核承担此任务，负责重建和存储被切换掉之前的CPU 状态。

2、Linux下的调度类介绍（sched_class）

①、sched_class数据结构介绍

        调度类是内核调度框架中更为抽象的概念，它是一种组织和管理调度策略的结构化方式。在Linux内核中，每个调度类都对应一个具体的调度策略，或者一套相关的调度策略，并提供了一系列与调度相关的函数接口，如进程入队、出队、选择下一个运行进程等操作。

        sched_class结构体是在代码中体现调度类，描述了调度器的基本操作接口，内核根据不同调度策略（如CFS、实时调度等）实现了对应的调度类，这些调度类则通过实现下面的接口来参与到内核的整体调度流程中。

        数据结构定义在kernel/sched/sched.h

struct sched_class {
 
#ifdef CONFIG_UCLAMP_TASK
	int uclamp_enabled;
#endif
	/* 将进程加入到执行队列当中，即将调度实体(进程)存放到红黑树中，并对nr_running变量自动会加1*/
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
 
	/* 从执行队列当中删除进程，并对nr_running变量自动减1 */
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	
	/*放弃CPU执行权，实际上该函数执行先出队后入队，在这种情况下，它直接将调度实体放在红黑树的最右端 */
	void (*yield_task)   (struct rq *rq);
	bool (*yield_to_task)(struct rq *rq, struct task_struct *p);
	
	/* 用于检查当前进程是否可被新进程抢占 */
	void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
	
	/* 选择下一个应用要运行的进程*/
	struct task_struct *(*pick_next_task)(struct rq *rq);
	
	/*将进程放回到运行队列当中 */
	void (*put_prev_task)(struct rq *rq, struct task_struct *p);
	void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
 
#ifdef CONFIG_SMP
	int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
 
	/* 为进程选择一个合适的CPU */
	int  (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
	struct task_struct * (*pick_task)(struct rq *rq);
	
	/* 迁移任务到另一个CPU */
	void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
	
	/*专门用于唤醒进程 */
	void (*task_woken)(struct rq *this_rq, struct task_struct *task);
	
	/* 修改进程在CPU的亲和力 */
	void (*set_cpus_allowed)(struct task_struct *p,
				 const struct cpumask *newmask,
				 u32 flags);
	
	/* 启动运行队列 */
	void (*rq_online)(struct rq *rq);
	
	/* 禁止运行队列 */
	void (*rq_offline)(struct rq *rq);
	struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
#endif
	/* 调用自time_tick函数，它可能引起进程切换，将驱动运行时(running)抢占 */
	void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
 
	/* 当进程创建的时候调用、不同调度策略的进程初始化也是不一样的*/
	void (*task_fork)(struct task_struct *p);
	
	/* 进程退出的时候使用*/
	void (*task_dead)(struct task_struct *p);
 
	/*
	 * The switched_from() call is allowed to drop rq->lock, therefore we
	 * cannot assume the switched_from/switched_to pair is serialized by
	 * rq->lock. They are however serialized by p->pi_lock.
	 */
	/* 专门用于进程的切换*/
	void (*switched_from)(struct rq *this_rq, struct task_struct *task);
	void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
	
	/*进程优先级的更改 */
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
			      int oldprio);
	unsigned int (*get_rr_interval)(struct rq *rq,
					struct task_struct *task);
	void (*update_curr)(struct rq *rq);
 
#ifdef CONFIG_FAIR_GROUP_SCHED
	/* */
	void (*task_change_group)(struct task_struct *p);
#endif
};

        比较重要的几个成员接口：

        enqueue_task: 向就绪队列添加一个进程，某个任务进入可运行状态时，该函数将会调用，它将调度实体放入到红黑树当中。

        dequeue_task: 将一个进程从就绪队列中进行删除，当某个任务退出可运行状态时调用该函数，将从红黑树中去掉对应调度实体。

        yield_task:在进程想要资源放弃对处理器的控制权时，可使用在sched_yiled系统调用，会调用内核API去处理操作。

        check_preempt_curr: 检查当前运行的任务是否被抢占。

        pick_next_task: 选择下来要运行的最合适的实体 (进程)。

        put_prev_task: 用于另一个进程代替当前运行的进程。

        set_curr_task: 当任务修改它调用类或修改它的任务组时，将调用这个函数。

        task_tick: 在每次激活周期调度器时，由周期性调度器调用。

②、Linux下的五大调度类

        Linux内核中实例化了五个调度类，代码如下：

extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

        stop_sched_class 停机调度类: 优先级是最高的调度类，停机进程是优先级最高的进程，可以抢占所有其它进程，其他进程不可能抢占停机进程。

        dl_sched_class 指Deadline调度类，它指的是具有固定截止期限（deadline）的调度策略，这类策略适用于对完成时间有严格限制的任务

        rt_sched_class 表示实时调度类（Real-Time Scheduling Class），这是用于实时进程调度的策略，包括SCHED_FIFO（先进先出）和SCHED_RR（循环轮转）两种调度策略。实时进程在调度时可以获得更高的优先级，并能抢占其他非实时进程以保证及时响应。

        fair_sched_class 即完全公平调度类（Completely Fair Scheduler, CFS），它是Linux内核自2.6.23以来用于普通进程的标准调度策略。CFS设计的目标是在所有可运行进程之间公平地分配CPU时间，基于进程的动态优先级（由nice值和CPU使用时间等因素决定）进行调度。

        idle_sched_class 是空闲调度类，它负责调度idle任务，即idle进程。当系统的所有其他进程都不需要CPU时，idle进程会被调度执行，通常它的作用是降低CPU利用率，避免无谓的忙碌等待，并在必要时触发电源管理相关的操作。

③、调度器结构分析

        当处理器空闲时，它会向主调度器请求分配新任务，主调度器依据任务列表及其优先级等信息作出决策，通过上下文切换将CPU使用权转交给合适的任务。此外，周期性调度器定期唤醒主调度器以重新评估系统负载，并据此可能调整任务执行计划，如在高负载时减少低优先级任务执行，确保关键服务获得足够资源。

3、调度策略先级

        task_struct结构体中采用三个成员表示进程的优先级： prio 和 normal_prio 表示动态优先级 ,

        static_prio 表示进程的静态优先级。

        内核将任务优先级划分，实时优先级范围是0 到 MAX_RT_PRIO-1 （即 99 ），而普通进

程的静态优先级范围是从 MAX_RT_PRIO 到 MAX_PRIO-1 （即 100到139）。 代码定义在 Linux 内核源码： /include/linux/sched/prio.h 。

        实时进程与普通进程有着明确的优先级区间：实时进程的优先级范围是0至99，这类进程往往对应于对响应时间和执行效率要求极高的应用，比如音频视频流媒体播放、工业控制等领域。数字越小的实时进程享有更高的优先级，因此在争夺CPU资源时能优先得到执行。

        另一方面，普通进程的优先级设定在100至139之间，这类进程主要包括日常的非实时应用，如Web服务器、数据库管理系统等。同样遵循数值越小优先级越高的原则，即使在普通进程中，较小优先级的进程也会相对优先被执行。

4、调度策略

        Linux内核提供了一些调度策略用来选择调度器

        linux 内核调度策略源码： /include/uapi/linux/sched.h 。代码定义如下：

/*
 * Scheduling policies
 */
#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
#define SCHED_DEADLINE		6

SCHED_NORMAL：

        定义了正常进程调度策略，即非实时调度策略。在Linux内核中，使用完全公平调度器（Completely Fair Scheduler, CFS）来实现，它旨在为所有进程提供公平的CPU时间分配，依据进程的nice值（优先级）和虚拟运行时间来平衡各进程的执行机会。

SCHED_FIFO：

        代表先进先出（First In, First Out）的实时调度策略。在该策略下，实时进程按到达就绪队列的顺序执行，具有该调度策略的进程一旦获得CPU就不会被更低优先级的进程抢占，除非自身主动释放CPU，或者有更高优先级的SCHED_FIFO或SCHED_RR实时进程变得可运行。

SCHED_RR：

         轮转（Round Robin）实时调度策略，类似于SCHED_FIFO，但是实时进程在一个时间片（quantum）结束之后会被放置到同优先级实时进程队列的末尾，等待再次轮到自己执行，这样保证同一优先级的实时进程可以轮流获得执行机会。

SCHED_BATCH：

        批处理调度策略，适用于CPU密集型且对响应时间要求不高的批处理作业。使用此策略的进程会尽量减少上下文切换，从而提高CPU缓存的局部性并减少开销，有利于提高整体系统吞吐量。

SCHED_IDLE：

        空闲调度策略，应用于低优先级后台任务。这类任务只有在系统完全空闲时才会得到执行，不会影响其他任何进程的调度。

SCHED_DEADLINE：

        截止期限（Deadline）调度策略，专为那些有严格截止时间约束的进程设计。此类进程需要在预设的截止时间内完成计算任务，调度器会确保进程在规定时间内获得足够的CPU资源来满足其执行需求。

        SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE直接被映射到fair_sched_class

        SCHED_RR、SCHED_FIFO与rt_schedule_class进行相关联

5、调度器设计核心

        要理解这些复杂的调度器设计，我们必须要有一个核心主线，再去理解精髓。

        调度器需要解决的关键问题：

• 采用何种数据结构来组织进程以及如何实现pick next
• 如何根据进程优先级来确定进程运行时间
• 如何判断进程类型
  • 判断进程的交互性质，是否为IO密集
  • 奖励IO密集型&惩罚CPU密集型
  • 实时进程高优&普通进程低优
• 如何确定进程的动态优先级
  • 影响因素：静态优先级、nice值、IO密集型和CPU密集型产生的奖惩

        事实上，调度器在设计实现上考虑的问题还有很多，篇幅所限只列举几个公共问题。

二、完全公平调度器（Completely Fair Scheduler, CFS）

1、CFS概念和特性

        CFS全称为Completely Fair Scheduler（完全公平调度器），是Linux内核中用于普通（非实时）进程调度的主要算法，从Linux 2.6.23内核版本开始成为默认的调度策略。CFS的设计目标是确保所有进程在长期内都能公平地共享CPU资源，而不考虑进程的类型或历史执行情况。

CFS主要引入了下面几个特性：

        虚拟运行时间（vruntime）：CFS摒弃了传统固定时间片的轮转调度方式，转而使用虚拟运行时间来衡量进程的执行时间。每个进程在运行时，其虚拟运行时间会逐渐增加，未运行的进程则保持不变。调度器会比较所有进程的虚拟运行时间来决定下一个应该运行的进程，确保所有进程在虚拟运行时间上的相对差距反映其应该得到的CPU时间比例。

        权重计算：CFS根据进程的nice值（优先级）来调整其权重。nice值范围通常是从-20（最高优先级）到19（最低优先级，默认值为0）。nice值越高，进程的权重越小，意味着它在同等时间内获得的CPU份额越少，反之亦然。

        红黑树排序：CFS使用红黑树来组织就绪队列，进程节点按照其虚拟运行时间排序。每次调度时，会选择vruntime最小的进程执行，这样可以保证所有进程在长时间运行后达到近似的执行时间比例。

        动态优先级调整： 随着进程的执行，CFS会动态调整进程的优先级，确保即使在短时间段内也能表现得相对公平。当一个进程使用完其相对应的CPU时间后，其虚拟运行时间将会增加，从而降低其在红黑树中的优先级。

        其他特性：CFS还支持多核环境下的负载均衡，即在不同CPU间迁移进程以达到总体负载的均衡分布。此外，CFS设计时考虑了系统性能和电源管理，确保在兼顾公平性的同时，还能在适当时候将CPU资源交给idle进程，进而触发节能措施。

        完全公平调度算法（CFS）体现在对待每个进程都是公平的，让每个进程都运行一段相同的时间片，这就是基于时间片轮询调度算法。

        CFS定义一种新调度模型，它给cfs rg (cfs的run queue) 中的每一个进程都设置一个虚拟时钟-virtual runtime(vruntime)。如果一个进程得以执行，随着执行时间的不断增长，vruntime也将不断增大，没有得到执行的进程vruntime将保持不变。根据这种“不公平时间”也就是就绪队列中进程的等待时间分配CPU资源。

2、CFS如何实现“完全公平”

        在Linux内核的Completely Fair Scheduler (CFS)调度器中，真实运行时间和虚拟运行时间是用来衡量进程执行状况的两个重要概念：

        真实运行时间（Real Runtime）： 真实运行时间是指进程在物理CPU上实际消耗的时间，即从进程开始执行到目前为止，所经历的 wall clock 时间。这个时间包括进程在用户空间执行的时间（即进程执行指令的时间）以及在内核空间执行系统调用和服务的时间。真实运行时间是由系统时钟精确测量的，反映了进程实际占用CPU资源的情况。

        虚拟运行时间（Virtual Runtime, vruntime）： 虚拟运行时间在CFS调度器中是决定进程调度顺序的关键因素。它并不是指进程实际占用CPU的时间，而是经过权重调整后用来衡量进程“应当”消耗的CPU时间。CFS调度器根据每个进程的nice值、进程优先级和其他相关因素计算得出每个进程的虚拟运行时间，并用它来决定下一个将被执行的进程。在CFS调度器的红黑树结构中，虚拟运行时间最短的进程将被优先调度。

        在CFS中真实运行时间决定了进程对CPU资源占用时间，而虚拟运行时间只是决定了就绪队列中的调度次序。虚拟运行时间虽不直接影响进程实际占用CPU的时间长度，但确实决定了进程在就绪队列中的排序和调度器选择下一个进程的决策依据。在CFS调度策略下，通过维护虚拟运行时间，内核可以确保在长时段内，所有进程都能得到与其优先级和系统负载相对应的CPU时间分配，从而实现“完全公平”的调度效果。

3、虚拟运行时间和真实运行时间的计算

        举两个简单的例子加深理解一下虚拟运行时间和真实运行时间

        假设系统有两个进程A和B，初始时，它们的虚拟运行时间(vruntime)均为0。

        进程A的nice值为0（权重较高），进程B的nice值为1（权重较低）。

        假设一个时间片（tick）的长度为1ms。

        当进程A连续运行了5个时间片（即5ms）后，其真实运行时间为5ms。

        由于CFS调度器会根据权重调整虚拟运行时间的增长速率，此处假设进程A的权重是B的两倍，那么在这5ms内，进程A的虚拟运行时间增长比进程B更快。

        假设虚拟运行时间的增长与权重成反比（仅为简化举例），则在5ms后，进程A的虚拟运行时间增长了5ms，而进程B若也运行5ms，则其虚拟运行时间只增长了2.5ms（假设权重比为1:2，增长速度为A的一半）。

        在下次调度的时候会选择虚拟运行时间最短的进程进行调度

三、实时调度器类

1、实时调度类

1.1、概念

        实时调度类是Linux内核中专门为实时任务设计的调度策略集合。实时任务是指那些对响应时间有严格要求的应用程序或进程，必须在一定时限内完成特定任务，否则可能导致严重后果，如数据丢失、设备损坏、系统崩溃等。实时调度类确保这些任务能在任何时刻都能够获得足够的CPU资源，优先于非实时任务执行。

1.2、实时调度实体

struct sched_rt_entity {
	struct list_head		run_list;
	unsigned long			timeout;
	unsigned long			watchdog_stamp;
	unsigned int			time_slice;
	unsigned short			on_rq;
	unsigned short			on_list;
 
	struct sched_rt_entity		*back;
#ifdef CONFIG_RT_GROUP_SCHED
	struct sched_rt_entity		*parent;
	/* rq on which this entity is (to be) queued: */
	struct rt_rq			*rt_rq;
	/* rq "owned" by this entity/group: */
	struct rt_rq			*my_q;
#endif
} __randomize_layout;

run_list：list_head 类型的结构，这是一个双向链表头，用于将实时进程实体链接到其所在运行队列（rt_rq）的实时就绪队列列表中。当进程准备好运行时，它会被插入到这个链表中。

timeout：一个长整型变量，表示该实时进程下次可能超时的时间点。在实时调度中，尤其是对于SCHED_RR（轮转实时调度策略）中的进程，这个字段用于跟踪进程剩余的时间片。

watchdog_stamp：另一个长整型变量，通常用于记录实时进程上次被调度器监视的时间戳，它可以用于监控进程的执行是否超过预期时间，以防止死锁或其他调度异常。

time_slice：整型变量，表示实时进程在SCHED_RR调度策略下的时间片大小。在轮转调度中，每个实时进程在一个时间片结束时会被重新放回就绪队列的末尾等待再次调度。

on_rq 和 on_list：这两个 unsigned short 类型的标志位，用于标记实时进程调度实体是否已经加入到运行队列（runqueue，rq）或某种列表中。on_rq 通常用于指示进程是否正在运行队列上等待调度，而 on_list 可能用于记录进程在其他列表中的状态。

back：指向另一个 struct sched_rt_entity 的指针，用于在红黑树或其他数据结构中维护前后关系，方便在调度过程中遍历和查找。

parent 和 rt_rq：在支持实时进程组调度（CONFIG_RT_GROUP_SCHED）的配置下，parent 指针指向实时进程所属的父调度实体（如进程组的代表实体），rt_rq 指针则指向当前进程所在的实时运行队列。

my_q：也是一个指向 struct rt_rq 的指针，它代表了该实体拥有的或者“关联”的运行队列，可能在进程组调度时使用，表示该进程组或实体自身的资源队列。

1.3实时调度类

const struct sched_class rt_sched_class = {
	.next			= &fair_sched_class,
	.enqueue_task		= enqueue_task_rt,
	.dequeue_task		= dequeue_task_rt,
	.yield_task		= yield_task_rt,
 
	.check_preempt_curr	= check_preempt_curr_rt,
 
	.pick_next_task		= pick_next_task_rt,
	.put_prev_task		= put_prev_task_rt,
 
#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_rt,
 
	.set_cpus_allowed       = set_cpus_allowed_common,
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
	.task_woken		= task_woken_rt,
	.switched_from		= switched_from_rt,
#endif
 
	.set_curr_task          = set_curr_task_rt,
	.task_tick		= task_tick_rt,
 
	.get_rr_interval	= get_rr_interval_rt,
 
	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,
 
	.update_curr		= update_curr_rt,
};

.next: 指向下一个调度类，这里是&fair_sched_class，即完全公平调度类。这意味着在实时调度类无法调度任务时，会尝试转到公平调度类进行调度。

.enqueue_task: 指向enqueue_task_rt函数，用于将一个实时进程实体加入到运行队列（runqueue）中。

.dequeue_task: 指向dequeue_task_rt函数，用于从运行队列中移除一个实时进程实体。

.yield_task: 指向yield_task_rt函数，处理实时进程主动放弃CPU执行权的操作。

.check_preempt_curr: 指向check_preempt_curr_rt函数，检查当前运行的进程是否可以被新到达的实时进程抢占。

.pick_next_task: 指向pick_next_task_rt函数，用于选择下一个将要执行的实时进程。

.put_prev_task 和 .set_curr_task: 分别指向put_prev_task_rt和set_curr_task_rt函数，用于调度过程中的任务切换操作。

#ifdef CONFIG_SMP 部分:

.select_task_rq: 指向select_task_rq_rt函数，在多处理器（SMP）环境下，用于为进程选择合适的运行队列（CPU）。

.set_cpus_allowed: 指向set_cpus_allowed_common函数，用于设置进程允许运行的CPU集合。

.rq_online 和 .rq_offline: 分别指向rq_online_rt和rq_offline_rt函数，用于在线或离线运行队列时的处理。

.task_woken: 指向task_woken_rt函数，当实时进程被唤醒时调用。

.switched_from: 指向switched_from_rt函数，当进程从某CPU上下文切换出去时调用。

.task_tick: 指向task_tick_rt函数，在时钟节拍中断处理时调用，可能会触发进程调度。

.get_rr_interval: 指向get_rr_interval_rt函数，获取实时进程的时间片长度。

.prio_changed: 指向prio_changed_rt函数，实时进程优先级发生改变时调用。

.switched_to: 指向switched_to_rt函数，当进程被切换到CPU上准备执行时调用。

.update_curr: 指向update_curr_rt函数，用于更新当前正在运行的实时进程的相关信息。

1.4、实时调度类和调度实体之间的关系

        在Linux内核中，实时调度类定义了一套针对实时进程的调度算法和操作，而调度实体（如struct sched_rt_entity）则是这些算法操作的具体载体。每个实时进程都会封装在其对应的调度实体中，实时调度类通过调度实体来管理和调度这些实时进程，包括但不限于进程的入队、出队、优先级更改、时间片分配、抢占检查等一系列调度相关的操作。换言之，实时调度类提供了调度策略，而调度实体则是这些策略作用的具体对象。

2、实时调度类用到的调度策略

        SCHED_FIFO（先进先出实时调度策略）： 使用SCHED_FIFO策略的实时进程一旦获得CPU执行权，就会一直运行下去，直到该进程自愿放弃CPU（如调用了阻塞系统调用或显式释放CPU），或者有更高优先级的实时进程变得可运行。实时进程按照优先级排队，优先级高的进程始终排在优先级低的进程之前。

        SCHED_RR（轮转实时调度策略）： 类似于SCHED_FIFO，但每个SCHED_RR实时进程在执行完一个时间片（quantum）后，即使没有完成任务，也会被迫让出CPU给同一优先级的其他SCHED_RR进程。这样一来，同一优先级的实时进程能够实现时间片轮转，确保在紧迫性相同的情况下公平分配CPU时间。

        实时进程的优先级通常通过nice值来表示，但与非实时进程（采用CFS调度策略）的nice值不同，实时进程的优先级范围通常是0至MAX_RT_PRIO（通常是99，取决于内核配置）。优先级越高，表明该进程的实时性要求越强，获得CPU的可能性也就越大。