linux进程调度

调度策略

进程可以分为实时进程和普通进程，对于这两种不同类型的进程肯定有不同的调度策略，task_struct中的policy就用来表示调度策略。

// 调度策略
unsigned int policy;
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6

//优先级
int prio;
int static_prio;
int normal_prio;
unsigned int rt_priority;

此外为了配合调度策略，还为每个进程的task_struct中配有优先级，需要注意的是优先级数越小优先级越高，实时进程的优先级处于099之间，普通进程的优先级处于100139。

实时调度策略有SCHED_RR， SCHED_FIFO， SCHED_DEADLINE。

SCHED_FIFO，对于高优先级可以抢占低优先级，对于同等优先级先来先服务。

SCHED_RR，时间片轮转调度，也是高优先级可以抢占低优先级，对于同优先级新来的排到队尾，每个进程都执行一个时间片，然后换下一个进程。

普通调度策略有 SCHED_NORMAL， SCHED_BATCH，SCHED_IDLE

SCHED_NORMAL：普通的进程

SCHED_BATCH：后台进程

SCHED_IDLE：空闲时运行的进程

对于这些调度策略的执行逻辑都封装到task_struct中的sched_class中

const struct sched_class *sched_class;

seched_class的几个实现：

stop_sched_class：优先级最高的进程使用该策略，可以打断所有其他进程，并且该进程不会被抢占

rt_sched_class：RR算法或者FIFO算法的调度策略，具体由该进程的task_struct->policy决定。

fair_sched_class：普通进程的调度策略

CFS调度算法

CFS（completed fair Schedule）完全公平调度，适用于普通进程调度。

CFS为每个进程定义一个虚拟运行时间vruntime，每次总是选择vruntime最小的那个进程，进程得到处理机后变随着其运行时间的增加 增加其vruntime。

对于优先级的问题，对于高优先级的进程，vruntime增加慢一点，对于低优先级任务vruntime增加快一点，如此每次还是选择最小vruntime的那个进程，体现了其优先级。

vruntime = 实际运行时间 * NICE_0_LOAD / 权重

使用调度算法首先得有包含vruntime的调度实体，task_struct中有如下调度实体的成员变量：

struct sched_entity se; //完全调度实体
struct sched_rt_entity rt; // 实时调度实体
struct sched_dl_entity dl; // deadline调度实体

CFS算法中将se以其中的vruntime作为key存放到红黑树中，每次选择红黑树中最左端的结点即可。红黑树看做是一个队列，每次从中取进程。

完整调度

每颗cpu都有一个运行队列rq，这个队列中又存在多个子队列例如rt_rq(实时运行队列),cfs_rq。

当cpu需要一个任务执行时，其会先按照优先级选择不同的调度类，不同的调度类操作不同的队列，例如rt_sched_class先被调用，其会在rt_rq中找下一个任务，只有找不到时才轮到fair_sched_class被调用，它会在cfs_rq中寻找下一个任务。

完整结构如下：