做淘宝用那些网站发货,网站及app开发,服务器租用相关网站,装修公司网站源码目录
2.5 调度器的实现
2.5.1 概观
2.5.2 数据结构
2.5.3 处理优先级
2.5.3.1 nice和prior
2.5.3.2 vruntime
2.5.3.3 weight权重
2.5.4 核心调度器 2.5 调度器的实现
调度器的任务#xff1a; 1. 执行调度策略。 2. 执行上下文切换。 无论用户态抢占#xff0c;还是…目录
2.5 调度器的实现
2.5.1 概观
2.5.2 数据结构
2.5.3 处理优先级
2.5.3.1 nice和prior
2.5.3.2 vruntime
2.5.3.3 weight权重
2.5.4 核心调度器 2.5 调度器的实现
调度器的任务 1. 执行调度策略。 2. 执行上下文切换。 无论用户态抢占还是内核态抢占最终都调用schedule()函数执行调度操作实现进程切换。 调度分为主动调用周期调度 1. 主动调用schedule() 2. 周期调度时钟中断调用 一个进程一直while(1)不睡眠地执行任务就是通过时钟中断来调度其他进程的。 2.5.1 概观
CFS完全公平调度器调度器的一种。 红黑树上不是task_struct而是task_struct中的se成员即调度实体。 调试 #cat /proc/sched_debug 内容很多
2.5.2 数据结构 每个进程只能属于一个调度器。 常用调度器 CFS完全公平调度器用于普通进程。 实时调度器用于实时进程。 每种调度器通常都要实现 主调度器scheduler 周期调度器scheduler tick
struct task_struct {int prio; //调度器最终参考值通常等于normal_prio除非临时提高优先级RT_mutexint normal_prio; // CFS通过static_prio计算RT通过rt_priority计算int static_prio //用于普通进程范围100-139unsigned int rt_priority; //用于实时进程范围0-99struct sched_class *sched_class; //所属调度器类struct sched_entity se; //调度实体不是指针unsigned int policy; //SCHED_NORMAL/SCHED_IDLE /SCHED_BATCH /SCHED_RR/SCHED_FIFOcpumask_t cpus_allowed; 该进程可在哪些CPU上运行}
static_prio用于普通进程系统启动时分配可通过nice命令修改否则一直不变。 调度器类有 CFS 完全公平调度器。 struct sched_class fair_sched_class 普通进程使用 RT 实时调度器 struct sched_class rt_sched_class 实时进程使用 STOP struct sched_class stop_sched_class IDLE struct sched_class idle_sched_class 每种调度器类有各自策略policy CFS SCHED_NORMAL默认策略。 SCHED_IDLECPU空闲时才允许进程优先级较低。如后台任务 SCHED_BATCH批处理任务。 RT SCHED_RR基于时间片轮询。 SCHED_FIFO任务一直运行直到它自己主动放弃CPU。
struct sched_class { //每种调度器都要实现下列函数指针const struct sched_class *next;void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);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,struct task_struct *prev);void (*put_prev_task) (struct rq *rq, struct task_struct *p);int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);void (*migrate_task_rq)(struct task_struct *p, int next_cpu);void (*set_cpus_allowed)(struct task_struct *p, const struct cpumask *newmask);void (*rq_online)(struct rq *rq);void (*rq_offline)(struct rq *rq);void (*set_curr_task) (struct rq *rq);void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);};
enqueue_task将进程加入到就绪队列中。
dequeue_task从就绪队列中删除进程。
yield_task主动放弃CPU如CFS中会把调度实体放在红黑树最右端。
pick_next_task根据调度策略从就绪队列中选择下一个要执行的任务。
check_preempt_curr检查当前运行的进程是否应该被抢占以便让更高优先级的进程运行。
select_task_rq多核系统中为进程选择合适CPU。
set_curr_task更新当前正运行进程的调度信息。如修改调度策略更新统计信息。
task_tick系统周期性时钟中断时调用。用于更新进程的运行时间和统计信息。
struct rq { //运行队列即就绪队列每个CPU都有一个。unsigned long nr_running; //该CPU就绪的进程总数包括cfsRT就绪队列中进程unsigned long cpu_load[5]; //数组1 分钟、5 分钟、15 分钟等5个平均负载数据。struct load_weight load; //该CPU可运行进程的权重总和用于多处理器负载均衡。struct cfs_rq cfs; //cfs就绪队列struct rt_rq rt; //rt就绪队列struct task_struct *curr; //该CPU正运行的进程u64 clock;int cpu; //该就绪队列所属CPU}
idle、stop调度类的就绪队列管理方式不同所以struct rq中没有idlestop的子就绪队列。 每个CPU都有自身就绪队列定义方法 DECLARE_PER_CPU(struct rq, runqueues); 一个进程在同一时刻只能在一个CPU的struct rq中。 如何知道一个进程运行在哪个CPU task_struct - stack得到thread_infothread_info存储当前运行的CPU
struct thread_info {__u32 cpu;} 相关API 返回指定CPU的就绪队列 struct rq *rq cpu_rq(cpu); 返回当前CPU的就绪队列 struct rq *rq this_rq(); #define this_rq() (__get_cpu_var(runqueues)) 返回当前进程所在CPU的就绪队列 task_rq(p) 返回当前CPU正运行的进程 cpu_curr(cpu) 调度实体
struct sched_entity { //调度实体调度系统中代表一个进程被task_struct包含struct load_weight load; 负载权重struct rb_node run_node; 用于把调度实体连接到CFS就绪队列的红黑树unsigned int on_rq; 该调度实体是否在就绪队列上u64 exec_start; 当前实体上次被调度执行的时间u64 sum_exec_runtime; 当前实体总的执行时间update_curr函数会周期更新u64 vruntime; 虚拟运行时间用于在红黑树中排队决定调度先后顺序u64 prev_sum_exec_runtime;//sum_exec_runtime - prev_sum_exec_runtime就是进程本次在CPU上执行的时间。struct cfs_rq *cfs_rq; 当前调度实体属于的cfs_rqu64 nr_migrations; 迁移次数。多核中可能因为负载均衡而迁移到其它CPU上。};
通过se的struct rb_node run_node成员把进程挂在红黑树上被调度器从树的左边往右依次调度。
struct task_struct {struct sched_entity se;} CFS调度类的yield_task_fairenqueue_entityentity_tick函数指针都会调用update_curr函数
update_curr函数 用于计算和更新vruntime。 2.5.3 处理优先级
2.5.3.1 nice和prior
nice命令 作用更改普通进程的优先级对应static_prior不能用于实时进程。 nice值范围-20到19。 优先级范围 0-1390的优先级最高。 0-99实时进程的优先级。 100-139普通进程的优先级 static_prio nice值120 默认nice值为0默认static_prio120 struct task_struct {int static_prio //静态优先级普通进程范围100-139对应nice值-20 到19unsigned int rt_priority; //实时进程的优先级范围0-99int normal_prio; // CFS通过static_prio计算RT通过rt_priority计算int prio;} task_struct-static_prio 静态优先级即普通进程的优先级。 值范围100-139默认值为120。 计算static_prio NICE_TO_PRIO(nice); //即static_prio nice120 修改可通过nice命令或sched_setscheduler函数修改。 task_struct-rt_priority 实时优先级即实时进程的优先级。 值范围0-99 task_struct-normal_prio 普通优先级。 普通进程normal_prio static_prio 实时进程normal_prio 99 - rt_priority task_struct-prio 动态优先级。调度器最终使用。 计算通常直接等于normal_prio。 特殊情况 优先级反转低优先级进程A使用RT_mutex上锁后高优先级进程B等待该锁此时A进程临时拥有B进程的高优先级可让A尽早执行尽早释放锁。此时prio就不等于normal_prio。 总结如下图 修改普通进程的nice可影响运行时间比例。 应用层nice - prio - weight - 最终得到进程可运行时间比例。
2.5.3.2 vruntime
struct sched_entity {u64 vruntime;}
普通进程的CFS调度器使用而实时进程不用vruntime。 vruntime表示进程虚拟运行时间。 进程的vruntime值作用 决定了在CFS红黑树中的位置树的最左端节点的vruntime最小。 CFS调度器选择红黑树最左进程调度。 为什么叫虚拟运行时间 根据nice把实际运行时间放大缩小。 计算方法vruntime delta_exec * NICE_0_LOAD / weight delta_exec: 最近一次实际执行时间。 NICE_0_LOAD固定值。nice值为0对应的权重值 weight当前进程的nice值对应的权重值。 下节讲如何查找nice对应权重weight。 sum_exec_runtime更新 curr-se.sum_exec_runtime delta_exec; 撤销CPU时prev_exec_runtime sum_exec_runtime sum_exec_runtime不清0一直递增。 CFS起初为进程分配相同的vruntime子进程会继承父进程的vruntime。 当一个进程进入内核空间执行系统调用或发生中断时自动将处理器的状态信息包括通用寄存器、程序计数器PC、栈指针SP等保存到当前进程的内核栈中的pt_regs结构体中。 因为寄存器不一样所以不同CPU架构定义的struct pt_regs不一样。
x86架构
struct pt_regs {unsigned long ebx;unsigned long ecx;unsigned long edx;unsigned long esi;unsigned long edi;unsigned long ebp;unsigned long eax;unsigned long xds;unsigned long xes;unsigned long orig_eax;unsigned long eip;unsigned long xcs;unsigned long eflags;unsigned long esp; 栈指针unsigned long xss;}; ARM架构
struct pt_regs {long uregs[18];};#define ARM_cpsr uregs[16]#define ARM_pc uregs[15]#define ARM_lr uregs[14]#define ARM_sp uregs[13]#define ARM_ip uregs[12]#define ARM_fp uregs[11]#define ARM_r10 uregs[10]#define ARM_r9 uregs[9]#define ARM_r8 uregs[8]#define ARM_r7 uregs[7]#define ARM_r6 uregs[6]#define ARM_r5 uregs[5]#define ARM_r4 uregs[4]#define ARM_r3 uregs[3]#define ARM_r2 uregs[2]#define ARM_r1 uregs[1]#define ARM_r0 uregs[0]#define ARM_ORIG_r0 uregs[17] 2.5.3.3 weight权重
实时进程的权重比普通进程更高。
struct sched_entity { //被task_struct包含struct load_weight load;}struct load_weight {unsigned long weight; 权重用来确定进程运行时间比例unsigned long inv_weight; 权重倒数方便做除法计算};
根据进程prio值计算weight和inv_weight
void set_load_weight(struct task_struct *p){int prio p-static_prio - MAX_RT_PRIO; //MAX_RT_PRIO100struct load_weight *load p-se.load;load-weight prio_to_weight[prio]; 数组load-inv_weight prio_to_wmult[prio]; 数组}
通过prio_to_weight数组把prio转换为weight而weight最终影响CPU运行时间比例。
static const int prio_to_weight[40] { //将nice值转化为prio后作为数组index。/* -20 */ 88761, 71755, 56483, 46273, 36291,/* -15 */ 29154, 23254, 18705, 14949, 11916,/* -10 */ 9548, 7620, 6100, 4904, 3906,/* -5 */ 3121, 2501, 1991, 1586, 1277,/* 0 */ 1024, 820, 655, 526, 423,/* 5 */ 335, 272, 215, 172, 137,/* 10 */ 110, 87, 70, 56, 45,/* 15 */ 36, 29, 23, 18, 15,}; 数组nice/prio差1se的weight相差大约1.25倍即CPU时间比例相差1.25倍。 进程加入CPU就绪队列时把该进程权重加入CPU就绪队列总权重中。
进程从CPU就绪队列移除时就从CPU就绪队列总权重减去该进程权重。
const struct sched_class fair_sched_class {.enqueue_task enqueue_task_fair,.dequeue_task dequeue_task_fair,}enqueue_task_fair- enqueue_entity - update_load_add(cfs_rq-load, se-load.weight); CPU进程总权重用于多CPU间负载均衡。 参数/proc/sys/kernel/sched_latency_ns 即调度延迟或调度周期就绪队列的所有进程在该周期内至少有运行一次。 单位纳秒。 默认值2400000024毫秒 举例调度延迟是24毫秒如果有4个进程则每个进程可执行6毫秒。 参数/proc/sys/kernel/sched_min_granulariry_ns 即调度最小粒度每次调度后进程至少执行的时间。 单位纳秒。 默认值30000003毫秒 参数/proc/sys/kernel/sched_nr_latency 含义一个调度延迟周期内可处理的最大进程数。 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) 计算一个进程se在本轮调度周期应分得的真实运行时间。 计算公式 进程的时间片 (调度周期 ×(进程se权重 / CFS运行队列中进程权重总和)) __sched_period函数 作用获取调度周期值即sysctl_sched_latency /proc/sys/kernel/sched_latency_ns nice prior weight总结图 2.5.4 核心调度器
核心调度器分为 周期性调度器scheduler_tick 主调度器scheduler 周期性调度器scheduler_tick 时钟周期性调度器根据HZ自动调用。如果为了省电可关闭该调度器。 任务 1 更新调度器clock。 2. 更新当前runqueue的clock。用于辅助计算进程上次调度运行时长 3. 执行不同调度类中的task_tick回调函数。 curr-sched_class-task_tick(rq, curr); 周期任务有 CFS会更新进程vruntime 如果进程已执行足够时间或更高优先级的进程需运行时当前进程应立即让出CPU此时可给该进程thread_info中flag设置TIF_NEED_RESCHED标志位。 4. 更新该就绪队列的CPU load。 注意周期性调度器scheduler_tick不会去主动调度其他进程而是为当前进程设置TIF_NEED_RESCHED标志位tick时钟中断返回时检测到设置了该标志位则调度其他进程。 __sched前缀修饰的变量或函数 存储在对应elf文件中.sched.text段当coredump时可忽略.sched.text相关调用。 主调度器scheduler 1. preempt_disable( ); 关闭内核抢占 2. pick_next_task 选择下一个进程 3. context_switch 进程上下文切换包含 switch_mm : 加载新地址空间更新页表刷出TLB若是内核线程无需刷出TLB switch_to 从进程thread_info中保存的信息恢复CPU寄存器内核栈等。 进程的寄存器内容进入内核态时保存在它的内核栈中。 内核抢占 即是否让出CPU让别的进程执行。
如何判断需要抢占 检查进程thread_info的flags成员是否设置TIF_NEED_RESCHED若设置则让出CPU。 scheduler和scheduler_tick函数都会根据需要设置TIF_NEED_RESCHED标志。并在下一个抢占点到来时检查该标志调度其他进程完成抢占操作。 抢占点 中断处理程序的返回到内核态如时钟中断。 系统调用结束返回用户空间。 不允许抢占响应慢吞吐高。
允许抢占响应快吞吐低。 浪费部分CPU在进程切换所以导致吞吐低。 ARM中
struct thread_info {unsigned long flags;int preempt_count;}
flags的TIF_NEED_RESCHED标志 是否让出CPU让其他进程抢占。 preempt_count一个计数器。 大于 0 时即当前进程在临界区或执行关键操作禁止其他更高优先级的任务抢占当前线程。 等于0表示允许抢占。 举例 spin_lock函数将preempt_count1 spin_unlock函数preempt_count-1 一个进程用spin_lock上锁后不允许其他进程无法抢占当前进程。
每次内核前函数检查preempt_count值。 惰性FPU如果没有使用扩充寄存器如浮点寄存器不会保存和恢复。 举例A进程使用了浮点寄存器切换到B进程但B进程未使用不替换寄存器值节省恢复寄存器时间。
