linux之调度管理(2)-调度器 如何触发运行

一、调度器是如何在程序稳定运行的情况下进行进程调度的

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 指向其相应的调度类,调度器每次调度处理时,就通过当前进程的调度类函数进程操作,大大提高了可移植性和易修改性。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/8427.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

RHCE循环执行的例行性任务--crontab(周期性)

1.每分钟执行命令 2.每小时执行 3.每天凌晨3点半和12点半执行脚本 4.每隔6小时&#xff0c;相当于6,12,18,24点半执行脚本 5.30半点&#xff0c;8-18/2表示早上8点到下午18点之间每隔2小时执行脚本代表 6.每天晚上9点30重启nginx 7.每月1号和10号4点45执行脚本 8. 每周六和周日…

ETLCloud异常问题分析ai功能

在数据处理和集成的过程中&#xff0c;异常问题的发生往往会对业务运营造成显著影响。为了提高ETL&#xff08;提取、转换、加载&#xff09;流程的稳定性与效率&#xff0c;ETLCloud推出了智能异常问题分析AI功能。这一创新工具旨在实时监测数据流动中的潜在异常&#xff0c;自…

Java项目实战II基于Spring Boot的个人云盘管理系统设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 基于Spring Boot的个人云盘管理系统设计…

还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!

前言 程序员的终极追求是什么&#xff1f;当系统流量大增&#xff0c;用户体验却丝滑依旧&#xff1f;没错&#xff01;然而&#xff0c;在大量文件传输、数据传递的场景中&#xff0c;传统的“数据搬运”却拖慢了性能。为了解决这一痛点&#xff0c;Linux 推出了 零拷贝 技术&…

密码学是如何保护数据传输的安全性?

密码学通过一系列算法和协议来保护数据传输的安全性。 一、加密技术 对称加密算法 原理&#xff1a;使用相同的密钥进行加密和解密。应用&#xff1a;在数据传输过程中&#xff0c;发送方和接收方共享一个密钥&#xff0c;数据在传输前被加密&#xff0c;接收方使用相同的密钥…

python怎么打开py文件

1、首先在资源管理器里复制一下py文件存放的路径&#xff0c;按下windows键&#xff0b;r&#xff0c;在运行里输入cmd&#xff0c;回车打开命令行&#xff1a; 2、在命令行里&#xff0c;先切换到py文件的路径下面&#xff0c;接着输入“python 文件名.py ”运行python文件&a…

云计算——ACA学习 云计算核心技术

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 写在前面 本系列将会持续更新云计算阿里云ACA的学习&#xff0c;了解云计算及网络安全相关…

企业办公管理软件排名 | 九款企业管理软件助你制胜职场!(好用+实用+全面)

在寻找合适的企业办公管理软件时&#xff0c;你是否感到困惑不已&#xff0c;不知道从众多选项中选择哪一个&#xff1f; 一款好的管理软件不仅能简化工作流程&#xff0c;还能增强数据安全性&#xff0c;优化决策支持。 以下是九款备受推崇的企业管理软件&#xff0c;它们将助…

DNS服务器

DNS服务器 1、简介 DNS域名解析服务器&#xff0c;它作为将域名和IP地址相互映射的一个分布式数据库&#xff0c;端口号为53&#xff0c;通常使用UDP协议&#xff0c;但是在没有查询到完整的信息时&#xff0c;会以TCP这个协议来重新查询&#xff0c;所以在启动NDS服务器时&a…

顾荣辉在新加坡金融科技节发表主旨演讲:安全不仅是竞争优势,更是共同责任

在全球数字化和去中心化进程中&#xff0c;Web3的作用日益凸显&#xff0c;安全问题也日益成为行业的焦点。在这一背景下&#xff0c;顾荣辉教授于新加坡金融科技节&#xff08;SFF&#xff09;上发表主旨演讲《超越代码&#xff0c;引领信任》。顾教授在演讲中深入阐述了安全在…

Leetcode328奇偶链表,Leetcode21合并两个有序链表,Leetcode206反转链表 三者综合题

题目描述 思路分析 这题的思路就和我们的标题所述一样&#xff0c;可以看作是这3个题的合并&#xff0c;但是稍微还有一点点区别 比如&#xff1a;奇偶链表这道题主要是偶数链在了奇数后面&#xff0c;字节这个的话是奇偶链表分离了 所以字节这题的大概思路就是&#xff1a; …

「Mac玩转仓颉内测版1」入门篇1 - Cangjie环境的搭建

本篇详细介绍在Mac系统上快速搭建Cangjie开发环境的步骤&#xff0c;涵盖VSCode的下载与安装、Cangjie插件的离线安装、工具链的配置及验证。通过这些步骤&#xff0c;确保开发环境配置完成&#xff0c;为Cangjie项目开发提供稳定的基础支持。 关键词 Cangjie开发环境搭建VSC…

2023数学分析【南昌大学】

计算 求极限 lim ⁡ n → ∞ ( 1 n 2 + 1 2 + 1 n 2 + 2 2 + ⋯ + 1 n 2 + n 2 ) \mathop{\lim }\limits_{n \to \infty } \left( \frac{1}{{\sqrt {n^2 + 1^2} }} + \frac{1}{{\sqrt {n^2 + 2^2} }} + \cdots + \frac{1}{{\sqrt {n^2 + n^2} }} \right) n→∞lim​(n2+12 ​1…

从技术创新到商业应用,智象未来(HiDream.ai)创新不止步

在人工智能领域的最新动态中&#xff0c;智象未来&#xff08;HiDream.ai&#xff09;公司&#xff0c;作为全球领先的多模态生成式人工智能技术先驱&#xff0c;已经引起了广泛的行业瞩目。该公司专注于深度学习和计算机视觉技术的融合&#xff0c;致力于开发和优化视觉多模态…

ssm基于Vue的戏剧推广网站+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码看文章最下面 需要定制看文章最下面 目 录 摘 要 I Abstract II 第1章 绪论 1 1.1 课题背景 1 1.2 课题意义 1 1.3 研究内容 1 第2…

利用泰勒公式近似计算10的平方根

文章目录 1. 泰勒公式是什么2、利用泰勒公式计算 10 \sqrt{10} 10 ​第 1 步&#xff1a;泰勒级数展开第 2 步&#xff1a;计算各阶导数第 3 步&#xff1a;在 x 9 x 9 x9 处计算各阶导数第 4 步&#xff1a;构建各阶泰勒展开式第 5 步&#xff1a;计算 f ( 10 ) f(10) f(1…

AI芯片:推动高性能计算场景的关键力量

​ 大家好&#xff0c;我是Shelly&#xff0c;一个专注于输出AI工具和科技前沿内容的AI应用教练&#xff0c;体验过300款以上的AI应用工具。关注科技及大模型领域对社会的影响10年。关注我一起驾驭AI工具&#xff0c;拥抱AI时代的到来。 AI工具集1&#xff1a;大厂AI工具【共2…

C语言--结构体详解

一.前言 为了保证文章的质量和长度&#xff0c;小编将会分两篇介绍&#xff0c;思维导图如下&#xff0c;本文主要讲解概念部分&#xff0c;其中关于结构体内存对齐、位段等更加详细的内容将会在下一篇加以介绍&#xff0c;希望大家有所收获&#x1f339;&#x1f339; 在C语言…

完整教学:胡须图像分割

胡须图像分割系统源码&#xff06;数据集分享 [yolov8-seg-act&#xff06;yolov8-seg-C2f-Parc等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Global Al lnnovatio…

LeetCode 热题100 之 栈

1.有效的括号 思路分析&#xff1a;我们可以使用栈&#xff08;stack&#xff09;来解决这个问题。栈是一种先进后出的数据结构&#xff0c;这与括号匹配的需求非常契合。 unordered_map<char, char> bracket_map&#xff1a;这个哈希表用来存储右括号与左括号的对应关系…