网站建设有前景吗,如何创建自己的网站链接,网站做301重定向的作用,天津宇昊建设集团有限公司网站一、调度器是如何在程序稳定运行的情况下进行进程调度的
1.1 系统定时器 因为我们主要讲解的是调度器#xff0c;而会涉及到一些系统定时器的知识#xff0c;这里我们简单讲解一下内核中定时器是如何组织#xff0c;又是如何通过通过定时器实现了调度器的间隔调度。首先我们…一、调度器是如何在程序稳定运行的情况下进行进程调度的
1.1 系统定时器 因为我们主要讲解的是调度器而会涉及到一些系统定时器的知识这里我们简单讲解一下内核中定时器是如何组织又是如何通过通过定时器实现了调度器的间隔调度。首先我们先看一下内核定时器的框架具体定时器的详解在其他文章中。 在内核中会使用strut clock_event_device结构描述硬件上的定时器每个硬件定时器都有其自己的精度会根据精度每隔一段时间产生一个时钟中断。而系统会让每个CPU使用一个tick_device描述系统当前使用的硬件定时器(因为每个CPU都有其自己的运行队列)通过tick_device所使用的硬件时钟中断进行时钟滴答(jiffies)的累加(只会有一个CPU负责这件事)并且在中断中也会调用调度器而我们在驱动中常用的低精度定时器就是通过判断jiffies实现的。而当使用高精度定时器(hrtimer)时情况则不一样hrtimer会生成一个普通的高精度定时器在这个定时器中回调函数是调度器其设置的间隔时间同时钟滴答一样。 所以在系统中每一次时钟滴答都会使调度器判断一次是否需要进行调度。
1.2 时钟中断 当时钟发生中断时首先会调用的是tick_handle_periodic()函数在此函数中又主要执行tick_periodic()函数进行操作。我们先看一下tick_handle_periodic()函数
//kernel/kernel/time/tick-common.c/** Event handler for periodic ticks*/
void tick_handle_periodic(struct clock_event_device *dev)
{/* 获取当前CPU */int cpu smp_processor_id();/* 获取下次时钟中断执行时间 */ktime_t next dev-next_event;tick_periodic(cpu);#if defined(CONFIG_HIGH_RES_TIMERS) || defined(CONFIG_NO_HZ_COMMON)/** The cpu might have transitioned to HIGHRES or NOHZ mode via* update_process_times() - run_local_timers() -* hrtimer_run_queues().*/if (dev-event_handler ! tick_handle_periodic)return;
#endif/* 如果是周期触发模式直接返回 */if (!clockevent_state_oneshot(dev))return;/* 为了防止当该函数被调用时clock_event_device中的计时实际上已经经过了不止一个tick周期这时候tick_periodic可能被多次调用使得jiffies和时间可以被正确地更新。 */for (;;) {/** Setup the next period for devices, which do not have* periodic mode:*//* 计算下一次触发时间 */next ktime_add(next, tick_period);/* 设置下一次触发时间返回0表示成功 */if (!clockevents_program_event(dev, next, false))return;/** Have to be careful here. If were in oneshot mode,* before we call tick_periodic() in a loop, we need* to be sure were using a real hardware clocksource.* Otherwise we could get trapped in an infinite* loop, as the tick_periodic() increments jiffies,* which then will increment time, possibly causing* the loop to trigger again and again.*/if (timekeeping_valid_for_hres())tick_periodic(cpu);}
}此函数主要工作是执行tick_periodic()函数然后判断时钟中断是单触发模式还是循环触发模式如果是循环触发模式则直接返回如果是单触发模式则执行如下操作
计算下一次触发时间设置下次触发时间如果设置下次触发时间失败则根据timekeeper等待下次tick_periodic()函数执行时间。返回第一步 而在tick_periodic()函数中程序主要执行路线为tick_periodic()-update_process_times()-scheduler_tick()。最后的scheduler_tick()函数则是跟调度相关的主要函数。我们在这具体先看看tick_periodic()函数和update_process_times()函数
tick_periodic:
//kernel/kernel/time/tick-common.c
/** Periodic tick*/
static void tick_periodic(int cpu)
{if (tick_do_timer_cpu cpu) {/*判断当前CPU是否负责更新时间 */raw_spin_lock(jiffies_lock);write_seqcount_begin(jiffies_seq);/* Keep track of the next tick event */tick_next_period ktime_add(tick_next_period, tick_period);do_timer(1);/* 更新 jiffies计数jiffies 1 */write_seqcount_end(jiffies_seq);raw_spin_unlock(jiffies_lock);update_wall_time();/* 更新墙上时间就是我们生活中的时间 */}/* 更新当前进程信息调度器主要函数 */update_process_times(user_mode(get_irq_regs()));profile_tick(CPU_PROFILING);
}tick_device 周期性调用此函数更新jiffies 和当前进程但是只有一个CPU是负责更新jiffies 和系统时间其他的CPU 只会负责更新自己的进程时间和调度。
update_process_times
// kernel/kernel/time/timer.c/** Called from the timer interrupt handler to charge one tick to the current* process. user_tick is 1 if the tick is user time, 0 for system.*/
void update_process_times(int user_tick)
{struct task_struct *p current;PRANDOM_ADD_NOISE(jiffies, user_tick, p, 0);/* Note: this timer irq context must be accounted for as well. *//* 更新当前进程的内核态和用户态占用率 */account_process_tick(p, user_tick);/* 检查有没有定时器到期有就运行到期定时器的处理 */run_local_timers();rcu_sched_clock_irq(user_tick);
#ifdef CONFIG_IRQ_WORKif (in_irq())irq_work_tick();
#endif/* 调度器的tick */scheduler_tick();if (IS_ENABLED(CONFIG_POSIX_TIMERS))run_posix_cpu_timers();
} 这两个函数主要工作为将jiffies加1、更新系统的墙上时间、更新当前进程的内核态和用户态的CPU占用率、检查是否有定时器到期运行到期的定时器。当执行完这些操作后就到了最重要的scheduler_tick()函数而scheduler_tick()函数主要做什么呢就是更新CPU和当前进行的一些数据然后根据当前进程的调度类调用task_tick()函数。这里普通进程调度类的task_tick()是task_tick_fair()函数。
// kernel/kernel/sched/core.c/** This function gets called by the timer code, with HZ frequency.* We call it with interrupts disabled.*/
void scheduler_tick(void)
{/* 获取当前CPU的ID */int cpu smp_processor_id();/* 获取当前CPU的rq队列 */struct rq *rq cpu_rq(cpu);/* 获取当前CPU的当前运行程序实际上就是current */struct task_struct *curr rq-curr;struct rq_flags rf;unsigned long thermal_pressure;/* 更新CPU调度统计中的本次调度时间 */arch_scale_freq_tick();sched_clock_tick();rq_lock(rq, rf);/* 更新该CPU的rq运行时间 */update_rq_clock(rq);/* 更新CPU的负载 */thermal_pressure arch_scale_thermal_pressure(cpu_of(rq));update_thermal_load_avg(rq_clock_thermal(rq), rq, thermal_pressure);//调用当前进程的调度类的 task_tick 回调函数curr-sched_class-task_tick(rq, curr, 0);calc_global_load_tick(rq);psi_task_tick(rq);rq_unlock(rq, rf);perf_event_task_tick();#ifdef CONFIG_SMPrq-idle_balance idle_cpu(cpu);trigger_load_balance(rq);
#endif
}CFS 调度类 task_tick():
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{struct cfs_rq *cfs_rq;struct sched_entity *se curr-se;/* 向上更新进程组时间片 */for_each_sched_entity(se) {cfs_rq cfs_rq_of(se);/* 更新当前进程运行时间并判断是否需要调度此进程 */entity_tick(cfs_rq, se, queued);}if (static_branch_unlikely(sched_numa_balancing))task_tick_numa(rq, curr);update_misfit_status(curr, rq);update_overutilized_status(task_rq(curr));
} 显然到这里最重要的函数应该是entity_tick()因为是这个函数决定了当前进程是否需要调度出去。我们必须先明确一点就是CFS调度策略是使用红黑树以进程的vruntime为键值进行组织的进程的vruntime越小越在红黑树的左边而每次调度的下一个目标就是红黑树最左边的结点上的进程。而当进程运行时其vruntime是随着实际运行时间而增加的但是不同权重的进程其vruntime增加的速率不同正在运行的进程的权重约大(优先级越高)其vruntime增加的速率越慢所以其所占用的CPU时间越多。而每次时钟中断的时候在entity_tick()函数中都会更新当前进程的vruntime值。当进程没有处于CPU上运行时其vruntime是保持不变的。
entity_tick
//kernel/kernel/sched/fair.c
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{/** Update run-time statistics of the current.*/update_curr(cfs_rq); /* 更新当前进程运行时间包括虚拟运行时间 *//** Ensure that runnable average is periodically updated.*/update_load_avg(cfs_rq, curr, UPDATE_TG);update_cfs_group(curr);#ifdef CONFIG_SCHED_HRTICK/** queued ticks are scheduled to match the slice, so dont bother* validating it and just reschedule.*/if (queued) {/* 若queued为1则当前运行队列的运行进程需要调度 */resched_curr_lazy(rq_of(cfs_rq));return;}/** dont let the period tick interfere with the hrtick preemption*/if (!sched_feat(DOUBLE_TICK) hrtimer_active(rq_of(cfs_rq)-hrtick_timer))return;
#endif/* 检查是否需要调度 */if (cfs_rq-nr_running 1)check_preempt_tick(cfs_rq, curr);
}之后的文章会详细说说CFS关于进程的vruntime的处理现在只需要知道是这样就好在entity_tick()中首先会更新当前进程的实际运行时间和虚拟运行时间这里很重要因为要使用更新后的这些数据去判断是否需要被调度。在entity_tick()函数中最后面的check_preempt_tick()函数就是用来判断进程是否需要被调度的其判断的标准有两个
先判断当前进程的实际运行时间是否超过CPU分配给这个进程的CPU时间如果超过则需要调度。再判断当前进程的vruntime是否大于下个进程的vruntime如果大于则需要调度。
清楚了这两个标准check_preempt_tick()的代码则很好理解了。
// kernel/kernel/sched/fair.cstatic void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{/* ideal_runtime为进程应该运行的时间* delta_exec为进程增加的实际运行时间* 如果delta_exec超过了ideal_runtime表示该进程应该让出CPU给其他进程*/unsigned long ideal_runtime, delta_exec;struct sched_entity *se;s64 delta;/* slice为CFS队列中所有进程运行一遍需要的实际时间 *//* ideal_runtime保存的是CPU分配给当前进程一个周期内实际的运行时间/*计算公式为: 一个周期内进程应当运行的时间 一个周期内队列中所有进程运行一遍需要的时间 * /*当前进程权重 / 队列总权重/* delta_exec保存的是当前进程增加使用的实际运行时间*/ideal_runtime sched_slice(cfs_rq, curr);delta_exec curr-sum_exec_runtime - curr-prev_sum_exec_runtime;/* 增加的实际运行实际 应该运行实际说明需要调度出去 */if (delta_exec ideal_runtime) {resched_curr_lazy(rq_of(cfs_rq));/** The current task ran long enough, ensure it doesnt get* re-elected due to buddy favours.*//* 如果cfs_rq队列的lastnextskip指针中的某个等于当前进程则清空cfs_rq队列中的相应指针 */clear_buddies(cfs_rq, curr);return;}/** Ensure that a task that missed wakeup preemption by a* narrow margin doesnt have to wait for a full slice.* This also mitigates buddy induced latencies under load.*/if (delta_exec sysctl_sched_min_granularity)return;/* 获取下一个调度进程的se */se __pick_first_entity(cfs_rq);/* 当前进程的虚拟运行时间 - 下个进程的虚拟运行时间 */delta curr-vruntime - se-vruntime;/* 当前进程的虚拟运行时间 大于 下个进程的虚拟运行时间说明这个进程还可以继续运行 */if (delta 0)return;/* 当前进程的虚拟运行时间 小于 下个进程的虚拟运行时间说明下个进程比当前进程更应该被CPU使用resched_curr_lazy函数用于标记当前进程需要被调度出去 */if (delta ideal_runtime)resched_curr_lazy(rq_of(cfs_rq));
}这里补充一下延迟抢占的概念resched_lazy
延迟抢占补丁的核心很简单它们添加了另一个标志 TIF_NEED_RESCHED_LAZY 它表示需要在某个时刻重新调度但不一定是立即。在延迟抢占模式 ( PREEMPT_LAZY ) 中大多数事件会设置新的标志而不是 TIF_NEED_RESCHED .什么时候去判断TIF_NEED_RESCHED_LAZY 标志内核的计时器滴答处理程序将检查是否设置了 TIF_NEED_RESCHED_LAZY在自愿抢占点和中断返回路径中只检查 TIF_NEED_RESCHED 。
resched_curr_lazy() - resched_curr() :
//kernel/kernel/sched/core.cvoid resched_curr(struct rq *rq)
{struct task_struct *curr rq-curr;int cpu;lockdep_assert_held(rq-lock);
/* 检查当前进程是否已经设置了调度标志如果是则不用再设置一遍直接返回 */if (test_tsk_need_resched(curr))return;/* 根据rq获取CPU */cpu cpu_of(rq);/* 如果CPU 当前CPU则设置当前进程需要调度标志 */if (cpu smp_processor_id()) {/* 设置当前进程需要被调度出去的标志这个标志保存在进程的thread_info结构上 */set_tsk_need_resched(curr);/* 设置CPU的内核抢占 */set_preempt_need_resched();return;}/* 如果不是处于当前CPU上则设置当前进程需要调度并通知其他CPU */if (set_nr_and_not_polling(curr))smp_send_reschedule(cpu);elsetrace_sched_wake_idle_without_ipi(cpu);
}到这里实际上如果进程需要被调度则已经被标记如果进程不需要被调度则继续执行。这里大家或许有疑问只标记了进程需要被调度但是为什么并没有真正处理它
此时代码执行是处于时钟中断中并不是进程上下文。进程调度的发生时机之一就是发生在中断返回时这里是在汇编代码中实现的从时钟中断返回去的时候会调用到汇编函数ret_from_sys_call在这个函数中会先检查调度标志被置位如果被置位则跳转至schedule()而schedule()最后调用到__schedule()这个函数进行处理。
//kernel/kernel/sched/core.casmlinkage __visible void __sched schedule(void)
{struct task_struct *tsk current;sched_submit_work(tsk);do {preempt_disable();__schedule(false, false);sched_preempt_enable_no_resched();} while (need_resched());sched_update_worker(tsk);
}
EXPORT_SYMBOL(schedule);....
static void __sched notrace __schedule(bool preempt, bool spinning_lock)
{/* prev保存换出进程(也就是当前进程)next保存换进进程 */struct task_struct *prev, *next;unsigned long *switch_count;unsigned long prev_state;struct rq_flags rf;struct rq *rq;int cpu;cpu smp_processor_id(); /* 获取当前CPU ID */rq cpu_rq(cpu);/* 获取当前CPU运行队列 */prev rq-curr; //获取当前进程schedule_debug(prev, preempt);if (sched_feat(HRTICK))hrtick_clear(rq);local_irq_disable();rcu_note_context_switch(preempt);/** Make sure that signal_pending_state()-signal_pending() below* cant be reordered with __set_current_state(TASK_INTERRUPTIBLE)* done by the caller to avoid the race with signal_wake_up():** __set_current_state(state) signal_wake_up()* schedule() set_tsk_thread_flag(p, TIF_SIGPENDING)* wake_up_state(p, state)* LOCK rq-lock LOCK p-pi_state* smp_mb__after_spinlock() smp_mb__after_spinlock()* if (signal_pending_state()) if (p-state state)** Also, the membarrier system call requires a full memory barrier* after coming from user-space, before storing to rq-curr.*/rq_lock(rq, rf);/* 队列上锁 */smp_mb__after_spinlock();/* Promote REQ to ACT */rq-clock_update_flags 1;update_rq_clock(rq);switch_count prev-nivcsw;/* 当前进程非自愿切换次数 *//** We must load prev-state once (task_struct::state is volatile), such* that:** - we form a control dependency vs deactivate_task() below.* - ptrace_{,un}freeze_traced() can change -state underneath us.*//** 当内核抢占时会置位thread_info的preempt_count的PREEMPT_ACTIVE位调用schedule()之后会 *清除PREEMPT_ACTIVE置位表明是从内核抢占进入到此的* preempt_count()是判断thread_info的preempt_count整体是否为0* prev-state大于0表明不是TASK_RUNNING状态**/prev_state prev-state;if ((!preempt || spinning_lock) prev_state) {/* 当前进程不为TASK_RUNNING状态并且不是通过内核态抢占进入调度 */if (signal_pending_state(prev_state, prev)) {prev-state TASK_RUNNING; /* 有信号需要处理置为TASK_RUNNING */} else {/* 没有信号挂起需要处理会将此进程移除运行队列 *//* 如果代码执行到此说明当前进程要么准备退出要么是处于即将睡眠状态 */prev-sched_contributes_to_load (prev_state TASK_UNINTERRUPTIBLE) !(prev_state TASK_NOLOAD) !(prev-flags PF_FROZEN);if (prev-sched_contributes_to_load)rq-nr_uninterruptible;/** __schedule() ttwu()* prev_state prev-state; if (p-on_rq ...)* if (prev_state) goto out;* p-on_rq 0; smp_acquire__after_ctrl_dep();* p-state TASK_WAKING** Where __schedule() and ttwu() have matching control dependencies.** After this, schedule() must not care about p-state any more.*/deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);if (prev-in_iowait) {atomic_inc(rq-nr_iowait);delayacct_blkio_start();}}switch_count prev-nvcsw;}/* 获取下一个调度实体这里的next的值会是一个进程而不是一个调度组在pick_next_task会递归选出一个进程 */next pick_next_task(rq, prev, rf);/* 清除当前进程的thread_info结构中的flags的TIF_NEED_RESCHED、TIF_NEED_RESCHED_LAZY和PREEMPT_NEED_RESCHED标志位这两个位表明其可以被调度调出(因为这里已经调出了所以这两个位就没必要了) */clear_tsk_need_resched(prev);clear_tsk_need_resched_lazy(prev);clear_preempt_need_resched();if (likely(prev ! next)) {rq-nr_switches; /* 该CPU运行队列切换次数加1 *//** RCU users of rcu_dereference(rq-curr) may not see* changes to task_struct made by pick_next_task().*/RCU_INIT_POINTER(rq-curr, next);/* 该CPU当前执行进程为新进程 *//** The membarrier system call requires each architecture* to have a full memory barrier after updating* rq-curr, before returning to user-space.** Here are the schemes providing that barrier on the* various architectures:* - mm ? switch_mm() : mmdrop() for x86, s390, sparc, PowerPC.* switch_mm() rely on membarrier_arch_switch_mm() on PowerPC.* - finish_lock_switch() for weakly-ordered* architectures where spin_unlock is a full barrier,* - switch_to() for arm64 (weakly-ordered, spin_unlock* is a RELEASE barrier),*/*switch_count;migrate_disable_switch(rq, prev);psi_sched_switch(prev, next, !task_on_rq_queued(prev));trace_sched_switch(preempt, prev, next);/* Also unlocks the rq: *//* 这里进行了进程上下文的切换 */rq context_switch(rq, prev, next, rf);} else {rq-clock_update_flags ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);rq_unpin_lock(rq, rf);__balance_callbacks(rq);
/* 这里意味着下个调度的进程就是当前进程释放锁不做任何处理 */raw_spin_unlock_irq(rq-lock);}
}在__schedule()中每一步的作用注释已经写得很详细了选取下一个进程的任务在__schedule()中交给了pick_next_task()函数而进程切换则交给了context_switch()函数。我们先看看pick_next_task()函数是如何选取下一个进程的
// kernel/kernel/sched/core.c/** Pick up the highest-prio task:*/
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{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, but only if the prev task wasnt of a* higher scheduling class, because otherwise those loose the* opportunity to pull in more work from other CPUs.*/if (likely(prev-sched_class fair_sched_class rq-nr_running rq-cfs.h_nr_running)) {/* 所有进程都处于CFS运行队列中所以就直接使用cfs的调度类 */p pick_next_task_fair(rq, prev, rf);if (unlikely(p RETRY_TASK))goto restart;/* Assumes fair_sched_class-next idle_sched_class */if (!p) {put_prev_task(rq, prev);p pick_next_task_idle(rq);}return p;}restart:put_prev_task_balance(rq, prev, rf);
/* 在其他调度类中包含有其他进程从最高优先级的调度类迭代到最低优先级的调度类并选择最优的进程运行 */for_each_class(class) {p class-pick_next_task(rq);if (p)return p;}/* The idle class should always have a runnable task: */BUG();
}在pick_next_task()中完全体现了进程优先级的概念首先会先判断是否所有进程都处于cfs队列中如果不是则表明有比普通进程更高优先级的进程(包括实时进程)。内核中是将调度类优先级c从高到低进行排列然后选择时从最高优先级的调度类开始找是否有进程需要调度如果没有会转到下一优先级调度类在代码27行所体现27行展开是
#define for_each_class(class) \for (class sched_class_highest; class; class class-next) 而调度类的优先级顺序为
调度类优先级顺序: stop_sched_class - dl_sched_class - rt_sched_class - fair_sched_class - idle_sched_class
在pick_next_task()函数中返回了选定的进程的进程描述符接下来就会调用context_switch()进行进程切换了 static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,struct task_struct *next, struct rq_flags *rf)
{prepare_task_switch(rq, prev, next);/** For paravirt, this is coupled with an exit in switch_to to* combine the page table reload and the switch backend into* one hypercall.*/arch_start_context_switch(prev);/** kernel - kernel lazy transfer active* user - kernel lazy mmgrab() active** kernel - user switch mmdrop() active* user - user switch*//* 如果新进程的内存描述符为空说明新进程为内核线程 */if (!next-mm) { // to kernelenter_lazy_tlb(prev-active_mm, next);next-active_mm prev-active_mm;if (prev-mm) // from usermmgrab(prev-active_mm);elseprev-active_mm NULL;} else { // to user/* 切换虚拟地址空间 */membarrier_switch_mm(rq, prev-active_mm, next-mm);/** sys_membarrier() requires an smp_mb() between setting* rq-curr / membarrier_switch_mm() and returning to userspace.** The below provides this either through switch_mm(), or in* case prev-active_mm next-mm through* finish_task_switch()s mmdrop().*/switch_mm_irqs_off(prev-active_mm, next-mm, next);/* 如果被切换出去的进程是内核线程 */if (!prev-mm) { // from kernel/* will mmdrop() in finish_task_switch(). */rq-prev_mm prev-active_mm;/* 归还借用的oldmm */prev-active_mm NULL;}}rq-clock_update_flags ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);prepare_lock_switch(rq, next, rf);/* Here we just switch the register state and the stack. *//* 切换寄存器和内核栈还会重新设置current为切换进去的进程 */switch_to(prev, next, prev);/* 同步 */barrier();return finish_task_switch(prev);
}到这里整个进程的选择和切换就已经完成了。
总结 对于CFS的一些计算和处理实时进程的处理等将在其他文章进行详细解释。
二、调度的时机 首先我们需要清楚什么样的进程会进入调度器进行选择就是处于TASK_RUNNING状态的进程而其他状态下的进程都不会进入调度器进行调度。系统发生调度的时机如下
调用cond_resched()时显式调用schedule()时从系统调用或者异常中断返回用户空间时从中断上下文返回用户空间时
当开启内核抢占(默认开启)时会多出几个调度时机如下
在系统调用或者异常中断上下文中调用preempt_enable()时(多次调用preempt_enable()时系统只会在最后一次调用时会调度)在中断上下文中从中断处理函数返回到可抢占的上下文时(这里是中断下半部中断上半部实际上会关中断而新的中断只会被登记由于上半部处理很快上半部处理完成后才会执行新的中断信号这样就形成了中断可重入, 但是即使是中断下半部, 也是不能够被调度的) 系统并不是每时每刻都允许调度的发生当处于中断期间的时候(无论是上半部还是下半部)调度是被系统禁止的之后中断过后才重新允许调度。而对于异常系统并不会禁止调度也就是在异常上下文中系统是有可能发生调度的。
三、数据结构的组织形式
因为普通进程使用的调度算法为CFS调度算法它是以红黑树为基础的调度算法其相比与实时进程的调度算法复杂很多而实时进程在组织结构上与普通进程没有太大差别算法也较为简单。组成形式 红色se则为当前CPU上正在执行的程序蓝色为下个将要执行的程序其实图中并不规范实际上当进程运行时会从红黑树中剥离出来然后设定下一个调度进程当进程运行时间结束时再重新放入红黑树中。而为什么CPU0上有两个蓝色将被调度进程将在组调度中解释。而为什么红黑树中又有一个子红黑树我们将在调度实体中解释。 四、组调度 我们知道linux是一个多用户系统如果有两个进程分别属于两个用户而进程的优先级不同会导致两个用户所占用的CPU时间不同这样显然是不公平的(如果优先级差距很大低优先级进程所属用户使用CPU的时间就很小)所以内核引入组调度。如果基于用户分组即使进程优先级不同这两个用户使用的CPU时间都为50%。这就是为什么图1 中CPU0有两个蓝色将被调度的程序如果task_group1中的运行时间还没有使用完而当前进程运行时间使用完后会调度task_group1中的下一个被调度进程相反如果task_group1的运行时间使用结束则调用上一层的下一个被调度进程。需要注意的是一个组调度中可能会有一部分是实时进程一部分是普通进程这也导致这种组要能够满足即能在实时调度中进行调度又可以在CFS调度中进行调度。 linux可以以以下两种方式进行进程的分组
用户ID按照进程的USER ID进行分组在对应的/sys/kernel/uid/目录下会生成一个cpu.share的文件可以通过配置该文件来配置用户所占CPU时间比例。cgourp(control group)生成组用于限制其所有进程比如我生成一个组(生成后此组为空里面没有进程)设置其CPU使用率为10%并把一个进程丢进这个组中那么这个进程最多只能使用CPU的10%如果我们将多个进程丢进这个组这个组的所有进程平分这个10%。
注意的是这里的进程组概念和fork调用所产生的父子进程组概念不一样文章所使用的进程组概念全为组调度中进程组的概念。
为了管理组调度内核引进了struct task_group结构如下
* 进程组用于实现组调度 */
struct task_group {/* 用于进程找到其所属进程组结构 */struct cgroup_subsys_state css;#ifdef CONFIG_FAIR_GROUP_SCHED/* CFS调度器的进程组变量在 alloc_fair_sched_group() 中进程初始化及分配内存 *//* 该进程组在每个CPU上都有对应的一个调度实体因为有可能此进程组同时在两个CPU上运行(它的A进程在CPU0上运行B进程在CPU1上运行) */struct sched_entity **se;/* 进程组在每个CPU上都有一个CFS运行队列(为什么需要稍后解释) */struct cfs_rq **cfs_rq;/* 用于保存优先级默认为NICE 0的优先级 */unsigned long shares;#ifdef CONFIG_SMPatomic_long_t load_avg;atomic_t runnable_avg;
#endif
#endif#ifdef CONFIG_RT_GROUP_SCHED/* 实时进程调度器的进程组变量同 CFS */struct sched_rt_entity **rt_se;struct rt_rq **rt_rq;struct rt_bandwidth rt_bandwidth;
#endifstruct rcu_head rcu;/* 用于建立进程链表(属于此调度组的进程链表) */struct list_head list;/* 指向其上层的进程组每一层的进程组都是它上一层进程组的运行队列的一个调度实体在同一层中进程组和进程被同等对待 */struct task_group *parent;/* 进程组的兄弟结点链表 */struct list_head siblings;/* 进程组的儿子结点链表 */struct list_head children;#ifdef CONFIG_SCHED_AUTOGROUPstruct autogroup *autogroup;
#endifstruct cfs_bandwidth cfs_bandwidth;
};
在struct task_group结构中最重要的成员为 struct sched_entity ** se 和 struct cfs_rq ** cfs_rq。在图1 中root_task_group与task_group1都只有一个它们在初始化时会根据CPU个数为se和cfs_rq分配空间即在task_group1和root_task_group中会为每个CPU分配一个se和cfs_rq同理用于实时进程的 struct sched_rt_entity ** rt_se 和 struct rt_rq ** rt_rq也是一样。为什么这样呢原因就是在多核多CPU的情况下同一进程组的进程有可能在不同CPU上同时运行所以每个进程组都必须对每个CPU分配它的调度实体(struct sched_entity 和 struct sched_rt_entity)和运行队列(struct cfs_rq 和 struct rt_rq)。
调度实体(struct sched_entity) 在组调度中也涉及到调度实体这个概念它的结构为struct sched_entity(简称se)就是图1 红黑树中的se。其实际上就代表了一个调度对象可以为一个进程也可以为一个进程组。对于根的红黑树而言一个进程组就相当于一个调度实体一个进程也相当于一个调度实体。我们可以先看看其结构如下
/* 一个调度实体(红黑树的一个结点)其包含一组或一个指定的进程包含一个自己的运行队列一个父亲指针一个指向需要调度的运行队列指针 */
struct sched_entity {/* 权重在数组prio_to_weight[]包含优先级转权重的数值 */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;/* 虚拟运行时间在时间中断或者任务状态发生改变时会更新* 其会不停增长增长速度与load权重成反比load越高增长速度越慢就越可能处于红黑树最左边被调度* 每次时钟中断都会修改其值* 具体见calc_delta_fair()函数*/u64 vruntime;/* 进程在切换进CPU时的sum_exec_runtime值 */u64 prev_sum_exec_runtime;/* 此调度实体中进程移到其他CPU组的数量 */u64 nr_migrations;#ifdef CONFIG_SCHEDSTATS/* 用于统计一些数据 */struct sched_statistics statistics;
#endif#ifdef CONFIG_FAIR_GROUP_SCHED/* 代表此进程组的深度每个进程组都比其parent调度组深度大1 */int depth;/* 父亲调度实体指针如果是进程则指向其运行队列的调度实体如果是进程组则指向其上一个进程组的调度实体* 在 set_task_rq 函数中设置*/struct sched_entity *parent;/* 实体所处红黑树运行队列 */struct cfs_rq *cfs_rq;/* 实体的红黑树运行队列如果为NULL表明其是一个进程若非NULL表明其是调度组 */struct cfs_rq *my_q;
#endif#ifdef CONFIG_SMP/* Per-entity load-tracking */struct sched_avg avg;
#endif
};
实际上红黑树是根据 struct rb_node 建立起关系的不过 struct rb_node 与 struct sched_entity 是一一对应关系也可以简单看为一个红黑树结点就是一个调度实体。可以看出在 struct sched_entity 结构中包含了一个进程(或进程组)调度的全部数据其被包含在 struct task_struct 结构中的se中如下
struct task_struct {......../* 表示是否在运行队列 */int on_rq;/* 进程优先级* prio: 动态优先级范围为100~139与静态优先级和补偿(bonus)有关* static_prio: 静态优先级static_prio 100 nice 20 (nice值为-20~19,所以static_prio值为100~139)* normal_prio: 没有受优先级继承影响的常规优先级具体见normal_prio函数跟属于什么类型的进程有关*/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;
#ifdef CONFIG_CGROUP_SCHED/* 指向其所在进程组 */struct task_group *sched_task_group;
#endif........
}
在 struct sched_entity 结构中值得我们注意的成员是
load权重通过优先级转换而成是vruntime计算的关键。on_rq表明是否处于CFS红黑树运行队列中需要明确一个观点就是CFS运行队列里面包含有一个红黑树但这个红黑树并不是CFS运行队列的全部因为红黑树仅仅是用于选择出下一个调度程序的算法。很简单的一个例子普通程序运行时其并不在红黑树中但是还是处于CFS运行队列中其on_rq为真。只有准备退出、即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假。vruntime虚拟运行时间调度的关键其计算公式一次调度间隔的虚拟运行时间 实际运行时间 * (NICE_0_LOAD / 权重)。可以看出跟实际运行时间和权重有关红黑树就是以此作为排序的标准优先级越高的进程在运行时其vruntime增长的越慢其可运行时间相对就长而且也越有可能处于红黑树的最左结点调度器每次都选择最左边的结点为下一个调度进程。注意其值为单调递增在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小最小的将被调度。cfs_rq此调度实体所处于的CFS运行队列。my_q如果此调度实体代表的是一个进程组那么此调度实体就包含有一个自己的CFS运行队列其CFS运行队列中存放的是此进程组中的进程这些进程就不会在其他CFS运行队列的红黑树中被包含(包括顶层红黑树也不会包含他们他们只属于这个进程组的红黑树)。 对于怎么理解一个进程组有它自己的CFS运行队列其实很好理解比如在根CFS运行队列的红黑树上有一个进程A一个进程组B各占50%的CPU对于根的红黑树而言他们就是两个调度实体。调度器调度的不是进程A就是进程组B而如果调度到进程组B进程组B自己选择一个程序交给CPU运行就可以了而进程组B怎么选择一个程序给CPU就是通过自己的CFS运行队列的红黑树选择如果进程组B还有个子进程组C原理都一样就是一个层次结构。
而在 struct task_struct 结构中我们注意到有个调度类里面包含的是调度处理函数它具体如下
struct sched_class {/* 下一优先级的调度类* 调度类优先级顺序: stop_sched_class - dl_sched_class - rt_sched_class - fair_sched_class - idle_sched_class*/const struct sched_class *next;/* 将进程加入到运行队列中即将调度实体进程放入红黑树中并对 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在 compat_yield sysctl 关闭的情况下该函数实际上执行先出队后入队在这种情况下它将调度实体放在红黑树的最右端 */void (*yield_task) (struct rq *rq);bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);/* 检查当前进程是否可被新进程抢占 */void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);/** It is the responsibility of the pick_next_task() method that will* return the next task to call put_prev_task() on the prev task or* something equivalent.** May return RETRY_TASK when it finds a higher prio class has runnable* tasks.*//* 选择下一个应该要运行的进程运行 */struct task_struct * (*pick_next_task) (struct rq *rq,struct task_struct *prev);/* 将进程放回运行队列 */void (*put_prev_task) (struct rq *rq, struct task_struct *p);#ifdef CONFIG_SMP/* 为进程选择一个合适的CPU */int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);/* 迁移任务到另一个CPU */void (*migrate_task_rq)(struct task_struct *p, int next_cpu);/* 用于上下文切换后 */void (*post_schedule) (struct rq *this_rq);/* 用于进程唤醒 */void (*task_waking) (struct task_struct *task);void (*task_woken) (struct rq *this_rq, struct task_struct *task);/* 修改进程的CPU亲和力(affinity) */void (*set_cpus_allowed)(struct task_struct *p,const struct cpumask *newmask);/* 启动运行队列 */void (*rq_online)(struct rq *rq);/* 禁止运行队列 */void (*rq_offline)(struct rq *rq);
#endif/* 当进程改变它的调度类或进程组时被调用 */void (*set_curr_task) (struct rq *rq);/* 该函数通常调用自 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);/* 用于进程切换 */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_SCHEDvoid (*task_move_group) (struct task_struct *p, int on_rq);
#endif
}; 这个调度类具体有什么用呢实际上在内核中不同的调度算法它们的操作都不相同为了方便修改、替换调度算法使用了调度类每个调度算法只需要实现自己的调度类就可以了CFS算法有它的调度类SCHED_FIFO也有它自己的调度类当一个进程创建时用什么调度算法就将其 task_struct-sched_class 指向其相应的调度类调度器每次调度处理时就通过当前进程的调度类函数进程操作大大提高了可移植性和易修改性。
