unsigned long nr_uninterruptible;
下面幾個指針分別指向當前運行的進程、空閑進程、被停止運行的進程
struct task_struct *curr, *idle, *stop;
unsigned long next_balance;
struct mm_struct *prev_mm;進程切換時存放被替換進程內存描述符
字段clock用于實現就緒隊列自身的時鐘，每次調用周期性調度器時，都會更新clock的值。內核還提供了函數update_rq_clock，可在操作就緒隊列的調度中多次調用。
u64 clock;
......
};
調度類結構體在文件include/linux/sched.h中定義，如下：
struct sched_class {
next字段將各個調度類按重要性鏈接起來，最重要的是實時進程，其次是完全公平進程，再次是空閑進程
const struct sched_class *next;
向就緒隊列添加一個新進程，在進程從睡眠狀態(tài)變?yōu)榭蛇\行狀態(tài)調用該操作
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
將一個進程從就緒隊列中去除。
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
當進程志愿放棄對處理器的控制權時，可使用系統(tǒng)調用sched_yield，這將導致內核調用
函數yield_task
void (*yield_task) (struct rq *rq);
進程放棄CPU控制權并將控制權交給p進程
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);
選擇下一個需要運行的進程
struct task_struct * (*pick_next_task) (struct rq *rq);
通知調度器類當前運行的進程將要被另一個進程代替。
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
......
用于設置調度隊列的當前進程，例如cfs_rq->curr
void (*set_curr_task) (struct rq *rq);
由周期性調度器調用，更新一些時間統(tǒng)計量
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
當新進程創(chuàng)建時調用初始化一些特定調度器類的東西，并設置重調度標志TIF_NEED_RESCHED
void (*task_fork) (struct task_struct *p);
......
};
調度器操作比進程更一般的實體，每個進程描述結構中都嵌有一個調度實體結構，但并不是一個調度實體就等于一個進程，有時候將一組進程集合起來表示一個調度實體。調度實體結構在文件include/linux/sched.h中定義，如下：
struct sched_entity {
load記錄一個調度實體負荷權重
struct load_weight load; /* for load-balancing */
紅黑樹節(jié)點，使得實體可以在紅黑樹上排序
struct rb_node run_node;
用于鏈接到就緒隊列的cfs_tasks字段上
struct list_head group_node;
表示實體是否在就緒隊列上
unsigned int on_rq;
當新進程被加入就緒隊列或者在周期性調度器中，會計算當前值和exec_start之間的差值，將差值加到sum_exec_runtime中，exec_start則更新為當前時間
u64 exec_start;
記錄消耗的CPU時間
u64 sum_exec_runtime;
保存進程的虛擬時間，關于虛擬時間后面講詳細講解
u64 vruntime;
當進程失去CPU控制權時將sum_exec_runtime保存到prev_sum_exec_runtime中
u64 prev_sum_exec_runtime;
......
下面是跟組調度相關的字段
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *parent; 建立組調度中調度實體的層次關系
struct cfs_rq *cfs_rq; 組所屬的調度隊列
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;組內部的調度隊列
#endif
};
2 優(yōu)先級與負荷權重2.1優(yōu)先級的計算
前面講過優(yōu)先級有3個，static_prio、normal_prio和prio。Static_prio在進程啟動時靜態(tài)設置可用nice系統(tǒng)調用修改；normal_prio與靜態(tài)優(yōu)先級和調度策略有關，調度策略可能被修改；prio是調度算法中用到的優(yōu)先級，他可能被內核臨時改變，比如一個高優(yōu)先級的進程在使用的互斥量，被一個低優(yōu)先級進程占據了，這是就要臨時提高低優(yōu)先級的優(yōu)先級，這個優(yōu)先級就保存在prio中。
在用戶空間中，用nice系統(tǒng)調用設置進程的靜態(tài)優(yōu)先級，該nice值的范圍是-20到19之間，值越低優(yōu)先級越高。內核內部表示優(yōu)先級的的范圍是0到139，同樣也是值越低優(yōu)先級越高。從0到99專事實進程使用。Nice值-20到19映射的范圍是100到139.
優(yōu)先級prio的獲取是通過函數effective_prio來實現的，如下：
程序首先計算進程的普通優(yōu)先級然后判斷進程的優(yōu)先級是否小于MAX_RT_PRIO，這里并不考慮調度策略。如果進程優(yōu)先級在實時進程優(yōu)先級范圍內就直接返回其優(yōu)先級（prio）否則返回其普通優(yōu)先級。
static int effective_prio(struct task_struct *p)
{
p->normal_prio = normal_prio(p);
if (!rt_prio(p->prio))
return p->normal_prio;
return p->prio;
}
【effective_prio--->normal_prio】
由于實時進程中，進程描述符p->rt_priority字段表示的優(yōu)先級是其數值越大優(yōu)先級越高，與內核內部表示優(yōu)先級的方法剛好相反，所以在內核內部優(yōu)先級的計算方法是 MAX_RT_PRIO-1 - p->rt_priority;。函數__normal_prio僅僅是返回進程的靜態(tài)優(yōu)先級 return p->static_prio;。
static inline int normal_prio(struct task_struct *p)
{
int prio;
if (task_has_rt_policy(p))
prio = MAX_RT_PRIO-1 - p->rt_priority;
else
prio = __normal_prio(p);
return prio;
}
2.2 負荷權重的計算
進程每降低一個nice值，多獲得10%的CPU時間，每升高一個nice值，則放棄10%的CPU時間。為執(zhí)行該策略，內核將優(yōu)先級轉換為權重。優(yōu)先級--權重轉換表：
kernel/sched/sched.h
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
計算權重的函數是set_load_weight，空閑進程的權重最小。負荷權重包含在數據結構load_weight中如下：
struct load_weight {
unsigned long weight, inv_weight;
};
Weight表示優(yōu)先級在表prio_to_weight中映射的權重，inv_weight表示被負荷權重除的結果，這些值也存在表prio_to_wmult中，這個表與表prio_to_weight中的值一一對應。這些值的計算方法是(2^32/x)，x表示在表prio_to_weight中對應位置中的值。
static void set_load_weight(struct task_struct *p)
{
int prio = p->static_prio - MAX_RT_PRIO;
struct load_weight *load = &p->se.load;
if (p->policy == SCHED_IDLE) {
load->weight = scale_load(WEIGHT_IDLEPRIO);
load->inv_weight = WMULT_IDLEPRIO;
return;
}
load->weight = scale_load(prio_to_weight[prio]);
load->inv_weight = prio_to_wmult[prio];
}
3核心調度器
調度器的實現基于兩個函數：周期性調度器函數和主調度器函數。
周期性調度器函數scheduler_tick：在內核頻率HZ中斷處理函數中調用該函數。周期性調度函數的主要工作是更新各種時間統(tǒng)計量，在必要的時候進行進程 調度。在多CPU系統(tǒng)中它還進行負載均衡處理。
主調度器函數schedule：如果進程主動放棄執(zhí)行而選擇另一個活動進程運行就調用該函數。
周期性調度器函數和主調度器函數都不直接操作進程，而是調用進程所屬的操作類來操作進程。每個進程都屬于某個調度類（完全公平調度類、實時調度類）。
3.1 周期性調度器
kernel/sched/core.c
void scheduler_tick(void)
{
int cpu = smp_processor_id(); 獲取當前CPU的cpu id
struct rq *rq = cpu_rq(cpu);獲取當前CPU對應的就緒隊列結構
struct task_struct *curr = rq->curr;獲取當前進程的進程描述符
在函數update_rq_clock中，更新就緒隊列的兩個成員rq->clock_task，rq->clock。
update_rq_clock(rq);
函數update_cpu_load_active負責更新就緒隊列的cpu_load[]數組。將數組中先前存儲的負荷值向后移動一個位置，將當前就緒隊列的負荷計入數組的第一個位置。
update_cpu_load_active(rq);
調用當前進程所屬的調度類的task_tick函數，在該函數中更新一些時間計數，必要時調度其他活動進程來執(zhí)行。
curr->sched_class->task_tick(rq, curr, 0);
......
#ifdef CONFIG_SMP
rq->idle_balance = idle_cpu(cpu);
在多處理器系統(tǒng)中進行負載均衡，保證不同CPU的運行隊列包含數量基本相同的可運行進程
trigger_load_balance(rq, cpu);
#endif
}
3.2 主調度器
kernel/sched/core.c
asmlinkage void __sched schedule(void)
{
struct task_struct *tsk = current；
提交一些阻塞的IO請求避免死鎖。
sched_submit_work(tsk);
主調度器的組要工作都在函數__schedule中實現。
__schedule();
}
【schedule--->__schedule】
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
preempt_disable(); 禁止搶占
cpu = smp_processor_id(); 獲取當前進程CPU id
rq = cpu_rq(cpu);獲取當前cpu對應的就緒隊列結構
因為要切換到其他活動進程，所以當前進程就變成了“以前的”進程了。
prev = rq->curr;
......
保存進程切換計數
switch_count = &prev->nivcsw;
標志 PREEMPT_ACTIVE可以保證進程被搶占但是不被移除就緒隊列
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
如果進程有非阻塞掛起信號，而且狀態(tài)為TASK_INTERRUPTIBLE，就不將進程移除就緒隊列，并將其狀態(tài)設為TASK_RUNNING。
if (unlikely(signal_pending_state(prev->state, prev))) {
prev->state = TASK_RUNNING;
} else {
調用函數 p->sched_class->dequeue_task將進程移除隊列。
deactivate_task(rq, prev, DEQUEUE_SLEEP);
prev->on_rq = 0;
if (prev->flags & PF_WQ_WORKER) {
struct task_struct *to_wakeup;
每一個工作隊列都有一個工作者線程，如果當前進程是一個工作者線程，就查看是否有其他處于等待中的工作者線程，如果有在本地CPU上喚醒。
to_wakeup = wq_worker_sleeping(prev, cpu);
if (to_wakeup)
try_to_wake_up_local(to_wakeup);
}
}
switch_count = &prev->nvcsw;
}
如果CPU將變?yōu)榭臻e狀態(tài)，即就緒隊列上沒有可運行的進程，就試圖從其他CPU上可運行的進程移動到本地CPU的就緒隊列上。
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
通知調度器類當前運行的進程將要被另一個進程代替。
put_prev_task(rq, prev);
選擇下一個應該執(zhí)行的進程
next = pick_next_task(rq);
清除重調度標志TIF_NEED_RESCHED，重調度標志是由進程調度類設置的，表示調度請求，內核會在適當的時機完成該標志。
clear_tsk_need_resched(prev);
rq->skip_clock_update = 0;
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
++*switch_count; 遞增進程切換計數
完成進程上下文切換，下面詳細分析。
context_switch(rq, prev, next); /* unlocks the rq */
進程已經切換到其他進程去運行了，在后來的某個時候當前進程再次被調度時進程從這里開始運行，但是它在這中間可能已經被移動到其他CPU上了，所以此時棧上的cpu和rq變量的只可能就不一樣了。
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock);
post_schedule(rq);
sched_preempt_enable_no_resched();
if (need_resched())
goto need_resched;
}
【schedule--->__schedule--->context_switch】
static inline void context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next)
{
struct mm_struct *mm, *oldmm;
mm = next->mm;
oldmm = prev->active_mm;
如果將要運行的進程是一個內核線程，則它是沒有進程虛擬地址空間的，就將上一個進程的虛擬地址空間報保存到 next->active_mm 中，
if (!mm) {
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next);
} else
switch_mm(oldmm, mm, next); 更換虛擬內存上下文
如果前一個進程是內核線程就將前一個進程的prev->active_mm重置為NULL，rq->prev_mm指向上一個進程的虛擬地址空間
if (!prev->mm) {
prev->active_mm = NULL;
rq->prev_mm = oldmm;
}
......
進程寄存器和棧的切換，有特定體系架構的匯編實現。switch_to之后進程已經運行在了新進程之上，當前進程再次被調度運行時這中間可能已經經歷過很多次切換了，但是要保證prev指向上一個進程。這上一個進程可能并不是當前進程，所以要傳遞三個參數，下面代碼等效于prev=switch_to(next, prev);
switch_to(prev, next, prev);
barrier();
finish_task_switch(this_rq(), prev);
