之前的文章已經将排程器的資料結構、初始化、加入程序都進行了分析，這篇文章将主要說明排程器是如何在程式穩定運作的情況下進行程序排程的。
因為我們主要講解的是排程器，而會涉及到一些系統定時器的知識，這裡我們簡單講解一下核心中定時器是如何組織，又是如何通過通過定時器實作了排程器的間隔排程。首先我們先看一下核心定時器的架構
在核心中，會使用strut clock_event_device結構描述硬體上的定時器，每個硬體定時器都有其自己的精度，會根據精度每隔一段時間産生一個時鐘中斷。而系統會讓每個CPU使用一個tick_device描述系統目前使用的硬體定時器(因為每個CPU都有其自己的運作隊列)，通過tick_device所使用的硬體時鐘中斷進行時鐘滴答(jiffies)的累加(隻會有一個CPU負責這件事)，并且在中斷中也會調用排程器，而我們在驅動中常用的低精度定時器就是通過判斷jiffies實作的。而當使用高精度定時器(hrtimer)時，情況則不一樣，hrtimer會生成一個普通的高精度定時器，在這個定時器中回調函數是排程器，其設定的間隔時間同時鐘滴答一樣。
是以在系統中，每一次時鐘滴答都會使排程器判斷一次是否需要進行排程。
當時鐘發生中斷時，首先會調用的是tick_handle_periodic()函數，在此函數中又主要執行tick_periodic()函數進行操作。我們先看一下tick_handle_periodic()函數：
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 (dev->mode != CLOCK_EVT_MODE_ONESHOT)
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_device 周期性調用此函數
* 更新jffies和目前程序
* 隻有一個CPU是負責更新jffies的，其他的CPU隻會更新目前自己的程序
*/
static void tick_periodic(int cpu)
if (tick_do_timer_cpu == cpu) {
/* 目前CPU負責更新時間 */
write_seqlock(&jiffies_lock);
/* Keep track of the next tick event */
tick_next_period = ktime_add(tick_next_period, tick_period);
/* 更新 jiffies計數，jiffies += 1 */
do_timer(1);
write_sequnlock(&jiffies_lock);
/* 更新牆上時間，就是我們生活中的時間 */
update_wall_time();
/* 更新目前程序資訊，排程器主要函數 */
update_process_times(user_mode(get_irq_regs()));
profile_tick(CPU_PROFILING);
void update_process_times(int user_tick)
struct task_struct *p = current;
/* Note: this timer irq context must be accounted for as well. */
/* 更新目前程序的核心态和使用者态占用率 */
account_process_tick(p, user_tick);
/* 檢查有沒有定時器到期，有就運作到期定時器的處理 */
run_local_timers();
rcu_check_callbacks(cpu, user_tick);
#ifdef CONFIG_IRQ_WORK
if (in_irq())
irq_work_tick();
#endif
/* 排程器的tick */
scheduler_tick();
run_posix_cpu_timers(p);
這兩個函數主要工作為将jiffies加1、更新系統的牆上時間、更新目前程序的核心态和使用者态的CPU占用率、檢查是否有定時器到期，運作到期的定時器。當執行完這些操作後，就到了最重要的scheduler_tick()函數，而scheduler_tick()函數主要做什麼呢，就是更新CPU和目前進行的一些資料，然後根據目前程序的排程類，調用task_tick()函數。這裡普通程序排程類的task_tick()是task_tick_fair()函數。
void scheduler_tick(void)
/* 擷取目前CPU的ID */
/* 擷取目前CPU的rq隊列 */
struct rq *rq = cpu_rq(cpu);
/* 擷取目前CPU的目前運作程式，實際上就是current */
struct task_struct *curr = rq->curr;
/* 更新CPU排程統計中的本次排程時間 */
sched_clock_tick();
raw_spin_lock(&rq->lock);
/* 更新該CPU的rq運作時間 */
update_rq_clock(rq);
curr->sched_class->task_tick(rq, curr, 0);
/* 更新CPU的負載 */
update_cpu_load_active(rq);
raw_spin_unlock(&rq->lock);
perf_event_task_tick();
#ifdef CONFIG_SMP
rq->idle_balance = idle_cpu(cpu);
trigger_load_balance(rq);
/* rq->last_sched_tick = jiffies; */
rq_last_tick_reset(rq);
/*
* 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 (numabalancing_enabled)
task_tick_numa(rq, curr);
update_rq_runnable_avg(rq, 1);
顯然，到這裡最重要的函數應該是entity_tick()，因為是這個函數決定了目前程序是否需要排程出去。我們必須先明确一點就是，CFS排程政策是使用紅黑樹以程序的vruntime為鍵值進行組織的，程序的vruntime越小越在紅黑樹的左邊，而每次排程的下一個目标就是紅黑樹最左邊的結點上的程序。而當進行運作時，其vruntime是随着實際運作時間而增加的，但是不同權重的程序其vruntime增加的速率不同，正在運作的程序的權重約大(優先級越高)，其vruntime增加的速率越慢，是以其所占用的CPU時間越多。而每次時鐘中斷的時候，在entity_tick()函數中都會更新目前程序的vruntime值。當程序沒有處于CPU上運作時，其vruntime是保持不變的。
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_entity_load_avg(curr, 1);
update_cfs_rq_blocked_load(cfs_rq, 1);
update_cfs_shares(cfs_rq);
#ifdef CONFIG_SCHED_HRTICK
* queued ticks are scheduled to match the slice, so don't bother
* validating it and just reschedule.
/* 若queued為1，則目前運作隊列的運作程序需要排程 */
if (queued) {
/* 标記目前程序需要被排程出去 */
resched_curr(rq_of(cfs_rq));
* don't let the period tick interfere with the hrtick preemption
if (!sched_feat(DOUBLE_TICK) && hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
/* 檢查是否需要排程 */
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()的代碼則很好了解了。
* 檢查目前程序是否需要被搶占
* 判斷方法有兩種，一種就是判斷目前程序是否超過了CPU配置設定給它的實際運作時間
* 另一種就是判斷目前程序的虛拟運作時間是否大于下個程序的虛拟運作時間
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) {
/* 增加的實際運作實際 > 應該運作實際，說明需要排程出去 */
* The current task ran long enough, ensure it doesn't get
* re-elected due to buddy favours.
/* 清空cfs_rq隊列的last，next，skip指針 */
clear_buddies(cfs_rq, curr);
* 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)
/* 擷取下一個排程程序的se */
se = __pick_first_entity(cfs_rq);
/* 目前程序的虛拟運作時間 - 下個程序的虛拟運作時間 */
delta = curr->vruntime - se->vruntime;
/* 目前程序的虛拟運作時間 大于 下個程序的虛拟運作時間，說明這個程序還可以繼續運作 */
if (delta 0)
if (delta > ideal_runtime)
/* 目前程序的虛拟運作時間 小于 下個程序的虛拟運作時間，說明下個程序比目前程序更應該被CPU使用，resched_curr()函數用于标記目前程序需要被排程出去 */
* resched_curr - mark rq's current task 'to be rescheduled now'.
*
* On UP this means the setting of the need_resched flag, on SMP it
* might also involve a cross-CPU call to trigger the scheduler on
* the target CPU.
/* 标記目前程序需要排程，将目前程序的thread_info->flags設定TIF_NEED_RESCHED标記 */
void resched_curr(struct rq *rq)
int cpu;
lockdep_assert_held(&rq->lock);
/* 檢查目前程序是否已經設定了排程标志，如果是，則不用再設定一遍，直接傳回 */
if (test_tsk_need_resched(curr))
/* 根據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();
/* 如果不是處于目前CPU上，則設定目前程序需要排程，并通知其他CPU */
if (set_nr_and_not_polling(curr))
smp_send_reschedule(cpu);
else
trace_sched_wake_idle_without_ipi(cpu);
static void __sched __schedule(void)
/* prev儲存換出程序(也就是目前程序)，next儲存換進程序 */
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
need_resched:
/* 禁止搶占 */
preempt_disable();
/* 擷取目前CPU ID */
cpu = smp_processor_id();
/* 擷取目前CPU運作隊列 */
rq = cpu_rq(cpu);
rcu_note_context_switch(cpu);
prev = rq->curr;
schedule_debug(prev);
if (sched_feat(HRTICK))
hrtick_clear(rq);
* 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().
smp_mb__before_spinlock();
/* 隊列上鎖 */
raw_spin_lock_irq(&rq->lock);
/* 目前程序非自願切換次數 */
switch_count = &prev->nivcsw;
* 當核心搶占時會置位thread_info的preempt_count的PREEMPT_ACTIVE位，調用schedule()之後會清除，PREEMPT_ACTIVE置位表明是從核心搶占進入到此的
* preempt_count()是判斷thread_info的preempt_count整體是否為0
* prev->state大于0表明不是TASK_RUNNING狀态
*
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
/* 目前程序不為TASK_RUNNING狀态并且不是通過核心态搶占進入排程 */
if (unlikely(signal_pending_state(prev->state, prev))) {
/* 有信号需要處理，置為TASK_RUNNING */
prev->state = TASK_RUNNING;
} else {
/* 沒有信号挂起需要處理，會将此程序移除運作隊列 */
/* 如果代碼執行到此，說明目前程序要麼準備退出，要麼是處于即将睡眠狀态 */
deactivate_task(rq, prev, DEQUEUE_SLEEP);
prev->on_rq = 0;
/*
* If a worker went to sleep, notify and ask workqueue
* whether it wants to wake up a task to maintain
* concurrency.
*/
if (prev->flags & PF_WQ_WORKER) {
/* 如果目前程序處于一個工作隊列中 */
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev, cpu);
if (to_wakeup)
try_to_wake_up_local(to_wakeup);
}
}
switch_count = &prev->nvcsw;
/* 更新rq運作隊列時間 */
if (task_on_rq_queued(prev) || rq->skip_clock_update 0)
update_rq_clock(rq);
/* 擷取下一個排程實體，這裡的next的值會是一個程序，而不是一個排程組，在pick_next_task會遞歸選出一個程序 */
next = pick_next_task(rq, prev);
/* 清除目前程序的thread_info結構中的flags的TIF_NEED_RESCHED和PREEMPT_NEED_RESCHED标志位，這兩個位表明其可以被排程調出(因為這裡已經調出了，是以這兩個位就沒必要了) */
clear_tsk_need_resched(prev);
clear_preempt_need_resched();
rq->skip_clock_update = 0;
if (likely(prev != next)) {
/* 該CPU程序切換次數加1 */
rq->nr_switches++;
/* 該CPU目前執行程序為新程序 */
rq->curr = next;
++*switch_count;
/* 這裡進行了程序上下文的切換 */
context_switch(rq, prev, next); /* unlocks the rq */
* The context switch have flipped the stack from under us
* and restored the local variables which were saved when
* this task called schedule() in the past. prev == current
* is still correct, but it can be moved to another cpu/rq.
/* 新的程序有可能在其他CPU上運作，重新擷取一次CPU和rq */
cpu = smp_processor_id();
rq = cpu_rq(cpu);
raw_spin_unlock_irq(&rq->lock); /* 這裡意味着下個排程的程序就是目前程序，釋放鎖不做任何處理 */
/* 上下文切換後的處理 */
post_schedule(rq);
/* 重新打開搶占使能但不立即執行重新排程 */
sched_preempt_enable_no_resched();
if (need_resched())
goto need_resched;
在__schedule()中，每一步的作用注釋已經寫得很詳細了，選取下一個程序的任務在__schedule()中交給了pick_next_task()函數，而程序切換則交給了context_switch()函數。我們先看看pick_next_task()函數是如何選取下一個程序的：
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
const struct sched_class *class = &fair_sched_class;
struct task_struct *p;
* Optimization: we know that if all tasks are in
* the fair class we can call that function directly:
if (likely(prev->sched_class == class && rq->nr_running == rq->cfs.h_nr_running)) {
/* 所有程序都處于CFS運作隊列中，是以就直接使用cfs的排程類 */
p = fair_sched_class.pick_next_task(rq, prev);
if (unlikely(p == RETRY_TASK))
goto again;
/* assumes fair_sched_class->next == idle_sched_class */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev);
return p;
again:
/* 在其他排程類中包含有其他程序，從最高優先級的排程類疊代到最低優先級的排程類，并選擇最優的程序運作 */
for_each_class(class) {
p = class->pick_next_task(rq, prev);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
BUG(); /* the idle class will always have a runnable task */
在pick_next_task()中完全展現了程序優先級的概念，首先會先判斷是否所有程序都處于cfs隊列中，如果不是，則表明有比普通程序更高優先級的程序(包括實時程序)。核心中是将排程類重優先級高到低進行排列，然後選擇時從最高優先級的排程類開始找是否有程序需要排程，如果沒有會轉到下一優先級排程類，在代碼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 inline void
context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next)
struct mm_struct *mm, *oldmm;
prepare_task_switch(rq, prev, next);
mm = next->mm;
oldmm = prev->active_mm;
* 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);
if (!mm) {
/* 如果新程序的記憶體描述符為空，說明新程序為核心線程 */
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
/* 通知底層不需要切換虛拟位址空間
* if (this_cpu_read(cpu_tlbstate.state) == TLBSTATE_OK)
* this_cpu_write(cpu_tlbstate.state, TLBSTATE_LAZY);
enter_lazy_tlb(oldmm, next);
} else
/* 切換虛拟位址空間 */
switch_mm(oldmm, mm, next);
if (!prev->mm) {
/* 如果被切換出去的程序是核心線程 */
prev->active_mm = NULL;
/* 歸還借用的oldmm */
rq->prev_mm = oldmm;
* Since the runqueue lock will be released by the next
* task (which is an invalid locking op but in the case
* of the scheduler it's an obvious special-case), so we
* do an early lockdep release here:
spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
context_tracking_task_switch(prev, next);
/* 切換寄存器和核心棧，還會重新設定current為切換進去的程序 */
switch_to(prev, next, prev);
/* 同步 */
barrier();
* this_rq must be evaluated again because prev may have moved
* CPUs since it called schedule(), thus the 'rq' on its stack
* frame will be invalid.
finish_task_switch(this_rq(), prev);
到這裡整個程序的選擇和切換就已經完成了。
整個排程器大概原理和源碼已經分析完成，其他更多細節，如CFS的一些計算和處理，實時程序的處理等，将在其他文章進行詳細解釋。
![linux-svn解除安裝與安裝[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)