一、调度器是如何在程序稳定运行的情况下进行进程调度的
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 we're in oneshot mode,* before we call tick_periodic() in a loop, we need* to be sure we're 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 don't bother* validating it and just reschedule.*/if (queued) {/* 若queued为1,则当前运行队列的运行进程需要调度 */resched_curr_lazy(rq_of(cfs_rq));return;}/** don't 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 doesn't get* re-elected due to buddy favours.*//* 如果cfs_rq队列的last,next,skip指针中的某个等于当前进程,则清空cfs_rq队列中的相应指针 */clear_buddies(cfs_rq, curr);return;}/** Ensure that a task that missed wakeup preemption by a* narrow margin doesn't 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* can't 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 wasn't 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 指向其相应的调度类,调度器每次调度处理时,就通过当前进程的调度类函数进程操作,大大提高了可移植性和易修改性。