多任务⌗

多任务系统分为2类：

  • 非抢占式多任务系统，需要进程主动让出(yield)系统资源
  • 抢占式多任务系统，调度程序决定何时停止运行某个进程，大部分操作系统都是抢占式多任务系统

策略⌗

I/O消耗型和处理器消耗型进程⌗

  • I/O消耗型：进程大部分时间用来提交和等待I/O请求，经过短暂的可运行状态后会阻塞。
  • 处理器消耗型：进程大部分时间用在执行代码上，对于这类进程调度策略是降低它们的调度频率。

进程可能同时有两种特征。Linux为了保证交互式应用和桌面系统的性能，缩短进程响应时间，更倾向于优先调度I/O消耗型进程。

进程优先级⌗

最基本的调度策略，优先级高的进程先运行，低的后运行，相同优先级轮转运行，或者优先级高的进程时间片更长。注意：Linux没有完全采用基于优先级调度

Linux采用两种优先级范围，nice值和实时优先级。两种优先级不相交，任何实时进程的优先级都高于普通进程。

  • Nice值 -20到19，越小优先级越高
$ ps -el
F S   UID     PID    PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S     0       1       0  0  80   0 - 41913 -      ?        00:00:01 systemd
1 S     0       2       0  0  80   0 -     0 -      ?        00:00:00 kthreadd
1 I     0       3       2  0  60 -20 -     0 -      ?        00:00:00 rcu_gp
1 I     0       4       2  0  60 -20 -     0 -      ?        00:00:00 rcu_par_gp
1 I     0       6       2  0  60 -20 -     0 -      ?        00:00:00 kworker/0:0H-events_highpri
1 I     0       9       2  0  60 -20 -     0 -      ?        00:00:00 mm_percpu_wq
1 S     0      10       2  0  80   0 -     0 -      ?        00:00:00 rcu_tasks_rude_
1 S     0      11       2  0  80   0 -     0 -      ?        00:00:00 rcu_tasks_t

其中NI列表示
  • 实时优先级，0到99，越大优先级越高。实时优先级为99的进程优先级最高。
$ ps -eo state,uid,pid,ppid,rtprio,time,comm
S   UID     PID    PPID RTPRIO     TIME COMMAND
S     0       1       0      - 00:00:01 systemd
S     0       2       0      - 00:00:00 kthreadd
I     0       3       2      - 00:00:00 rcu_gp
I     0       4       2      - 00:00:00 rcu_par_gp
I     0       6       2      - 00:00:00 kworker/0:0H-events_highpri
I     0       9       2      - 00:00:00 mm_percpu_wq
S     0      10       2      - 00:00:00 rcu_tasks_rude_
S     0      11       2      - 00:00:00 rcu_tasks_trace
S     0      12       2      - 00:00:00 ksoftirqd/0
I     0      13       2      - 00:00:01 rcu_sched
S     0      14       2     99 00:00:00 migration/0
S     0      15       2     50 00:00:00 idle_inject/0

时间片⌗

时间片表示进程在被抢占前可以持续运行的时间，许多操作系统默认时间片10ms。Linux的CFS调度器没有直接分配时间片，而是将处理器的使用比划分给进程，在根据nice值加权。

调度策略的活动⌗

举了个例子，一个文本编辑器进程和一个视频解码进程，CFS调度器发现文本编辑器比视频解码运行的时间短得多，会让文本编辑器在需要时立刻抢占视频解码，处理用户的输入，而让视频解码进程在剩下的时刻运行。

Linux调度算法⌗

调度器类⌗

调度器是以模块的方式提供的，称为调度器类(scheduler classes)。一个调度器类可以用一种或者多种调度策略调度某一类进程, 也可以用于特殊情况或者调度特殊功能的进程。

有3个调度器类，优先级从高到低，存放在链表中：

  • rt_sched_class，包含SCHED_FIFO和SCHED_RR两个策略
  • fair_sched_class，也就是CFS调度类，包含SCHED_NORMAL和SCHED_BATCH两个策略
  • idle_sched_class，空闲进程

sched_class结构体定义如下：

struct sched_class {
	const struct sched_class *next;  // 调度器类链表

	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,
			      bool head);  // 将任务加入调度队列
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	void (*yield_task) (struct rq *rq);

	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);

    // 省略了SMP相关的函数指针

	void (*set_curr_task) (struct rq *rq);
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
	void (*task_fork) (struct task_struct *p);

	void (*switched_from) (struct rq *this_rq, struct task_struct *task,
			       int running);
	void (*switched_to) (struct rq *this_rq, struct task_struct *task,
			     int running);
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
			     int oldprio, int running);

	unsigned int (*get_rr_interval) (struct rq *rq,
					 struct task_struct *task);
    // 省略了组调度相关的函数指针
};

Unix中的进程调度⌗

进程调度器有两个通用的概念：

  • 优先级
  • 时间片

Unix中的优先级用nice值表示，直接将nice值映射到时间片会有几个问题

  • 如果将nice值映射到处理器的绝对时间

  • 问题1：如果要将nice值映射到时间片，就要将nice值对应到处理器的绝对时间，这将导致进程切换无法最优化进行。举个例子，假设nice值0对应100ms，nice值20对应5ms，那么前者获得20/21的时间，后者获得1/21的时间。如果两个nice值为20的进程，将在10秒内进行2次上下文切换，而两个nice值为0的进程，将在200秒内进行2次上下文切换。高nice值的进程通常是计算密集型任务，频繁切换是不合适的。

  • 问题2：相对nice值也有问题。举个例子，假设nice值0对应100ms，nice值1对应95ms。nice值18对应10ms，nice值19对应5ms。同时运行0和1的进程，他们分到的时间是差不多的，但是同时运行18和19进程，前者分到了后者两倍的时间。将nice值+-1带来的效果取决于nice值的大小，这是不合适的。

  • 问题3：将nice值映射到时间片必须是定时节拍tick的整数倍，例如10ms或1ms。系统定时器限制了两个时间片的差异，连续的nice值映射到时间片差别10ms或1ms。时间片会随定时器节拍改变。

  • 问题4：系统唤醒交互任务时会提升优先级，某些特殊进程会利用这一点获得更多处理器时间，打破公平性。

公平调度⌗

理想的完美多任务处理器 中，运行n个进程，每个进程可以获得1/n的时间，我们能在10ms内同时运行两个进程，他们各自使用处理器的一半时间，调度周期是无限小的。

真实的处理器 上无法同时运行多个进程，调度进程会有一定消耗，所以每个进程运行无限小的时间周期是不高效的。CFS为了解决这种消耗，运行每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个进程，而不采用分配时间片给每个进程的做法，nice值在CFS中用作权重。

CFS 为理想的多任务调度的无限小调度周期设立了一个近似值，称为 目标延迟 ，每个任务根据权重按比例分配，当任务数量趋于无限时，单个任务获得的时间片将趋于0，CFS为此引入了 最小粒度 时间片，默认1ms。CFS不是完美的公平调度，在系统中运行几百个可运行进程的时候相对而言比较公平。具体实现在kernel/sched_fair.c文件中。

Linux调度的实现⌗

4个重点：

  • 时间记账：struct sched_entity的vruntime字段记录进程的虚拟运行时间
  • 进程选择：用红黑树组织进程队列，选择具有最小vruntime的进程，
  • 调度器入口：schedule()函数，通过pick_next_task()选择最高优先级的sched_class调度器类，调度器类选择最高优先级的进程。
  • 睡眠和唤醒：通过等待队列实现，TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE状态的进程在同一个队列中。这里引出了伪唤醒(spurious wakeup)的概念。

调度实体sched_entity⌗ 

// 调度实体
struct sched_entity {
	struct load_weight	load;		/* for load-balancing */
	struct rb_node		run_node;   // 红黑树
	struct list_head	group_node;
	unsigned int		on_rq;

	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime;
	u64			prev_sum_exec_runtime;

	u64			last_wakeup;
	u64			avg_overlap;

	u64			nr_migrations;

	u64			start_runtime;
	u64			avg_wakeup;
}

// 任务结构体/进程描述符
struct task_struct {
    //... 
	int prio, static_prio, normal_prio; // 普通优先级
	unsigned int rt_priority;   // 实时优先级
	const struct sched_class *sched_class;  // 调度类
	struct sched_entity se;     // 调度实体
	struct sched_rt_entity rt;  // 实时进程调度实体
    unsigned int policy;    // 调度策略

    // ...
}

抢占和上下文切换⌗

schedule()函数调用context_switch()进行上下文切换，主要进行虚拟地址空间切换、保存、恢复栈信息和寄存器信息。

每个进程有need_resched标识，表示是否需要重新调度。

用户抢占⌗

在以下时刻发生：

  • 从系统调用返回用户空间时
  • 从终端处理程序返回用户空间时

内核抢占⌗

内核preempt_count计数器为0表示内核可以被抢占。

在以下时刻发生：

  • 中断处理程序正在执行，返回内核空间之前
  • 内核代码再一次可抢占的时候（preempt_count由非0变为0时）
  • 内核中的认为显式调用schedule()
  • 内核中的任务阻塞

实时调度策略⌗

SCHED_FIFO和SCHED_RR两种策略。

实时优先级范围从0到MAX_RT_PRIO（默认100），和普通进程的nice值共享取值范围，nice值被映射为MAX_RT_PRIO到MAX_RT_PRIO+40的范围内（默认-20～19映射为100～139）。

普通进程优先级（nice值）如下：

            <- higher priority
-20 ------------------------------------------ 19

实时进程优先级如下：

            higher priority ->
0 -------------------------------------------- 99

调度相关的系统调用⌗ 

// 调度策略和优先级相关的系统调用

nice();  // 修改nice值

sched_setscheduler();  // 设置进程的调度器
sched_getscheduler();  // 获取进程的调度器

sched_setparam();  // 设置进程的实时优先级
sched_getparam();  // 获取进程的实时优先级

sched_get_priority_max();  // 获取实时优先级的最大值
sched_get_priority_min();  // 获取实时优先级的最小值

sched_rr_get_interval();  // 获取进程的时间片值

// 处理器绑定相关的系统调用

sched_setaffinity();  // 设置进程的处理器亲和性
sched_getaffinity();  // 获取进程的处理器亲和性

// 让出处理器
sched_yield();

实验⌗

查看进程⌗ 

ps -eo state,uid,pid,ppid,rtprio,time,comm

查看调度策略⌗

chrt -p <pid>

例子：

chrt -p 8893

输出：

pid 8893's current scheduling policy: SCHED_OTHER
pid 8893's current scheduling priority: 0

查看6种调度策略

# 内核版本5.13.0-30-generic
chrt --help

输出：

 -b, --batch          set policy to SCHED_BATCH
 -d, --deadline       set policy to SCHED_DEADLINE
 -f, --fifo           set policy to SCHED_FIFO
 -i, --idle           set policy to SCHED_IDLE
 -o, --other          set policy to SCHED_OTHER
 -r, --rr             set policy to SCHED_RR (default)
  • SCHED_NORMAL和SCHED_BATCH调度普通的非实时进程
  • SCHED_FIFO和SCHED_RR和SCHED_DEADLINE则采用不同的调度策略调度实时进程
  • SCHED_IDLE则在系统空闲时调用idle进程.

修改调度策略⌗

例子：

chrt -p -o 0 8893
chrt -p -f 10 8893

参考⌗