進程調度相關內核結構
我們知道，進程運行需要各種各樣的系統資源，如內存、文件、打印機和最寶貴的 CPU 等，所以說，調度的實質就是資源的分配。系統通過不同的調度算法（Scheduling Algorithm）來實現這種資源的分配。通常來說，選擇什么樣的調度算法取決于資源分配的策略（Scheduling Policy）。
有關調度相關的結構保存在 task_struct 中，如下：
struct task_struct {
/*
task_struct 采用了如下3個成員表示進程的優先級，prio、normal_prio表示動態優先級
static_prio 為靜態優先級，靜態優先級是進程啟動時分配的優先級，它可以使用nice和sched_setscheduler系統調用修改，
否則在進程運行期間會一直保持恒定
*/
int prio, static_prio, normal_prio;
/*
sched_clas表示該進程所屬的調度器類
2.6.24版本中有3中調度類:
實時調度器 : rt_sched_class
完全公平調度器:fair_sched_class
空閑調度器: idle_sched_class
*/
const struct sched_class *sched_clas;
//調度實體
struct sched_entity se;
/*
policy 保存了對該進程應用的調度策略。
進程的調度策略有6種
SCHED_NORMAL SCHED_FIFO SCHED_RR SCHED_BATCH SCHED_IDLE
普通進程調度策略: SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE，這些都是通過完全公平調度器來處理的
實時進程調度策略: SCHED_RR、SCHED_FIFO 這些都是通過實時調度器來處理的
*/
unsigned int policy;
/*
除了內核線程（Kernel Thread），每個進程都擁有自己的地址空間（也叫虛擬空間），用mm_struct 來描述。active_mm是為內核線程而引入的。因為內核線程沒有自己的地址空間，
為了讓內核線程與普通進程具有統一的上下文切換方式，當內核線程進行上下文切換時，讓切換進來的線程的active_mm
指向剛被調度出去的進程的active_mm（如果進程的mm 域不為空，則其active_mm 域與mm 域相同）
*/
struct mm_struct *mm, *active_mm;
//表示實時進程的優先級，最低的優先級為0，最高為99，值越大，優先級越高
unsigned int rt_priority;
...
};
每個進程都擁有自己的地址空間（也叫虛擬空間），用 mm_struct 來描述。
active_mm 是為內核線程而引入的，因為內核線程沒有自己的地址空間，為了讓內核線程與普通進程具有統一的上下文切換方式，當內核線程進行上下文切換時，讓切換進來的線程的 active_mm 指向剛被調度出去的進程的 active_mm（如果進程的mm 域不為空，則其 active_mm 域與 mm 域相同）。
在 linux 2.6 中 sched_class 表示該進程所屬的調度器類有3種：
- 實時調度器 (RT，rt_sched_class) : 為每個優先級維護一個隊列；
- 完全公平調度器 (CFS，fair_sched_class) : 采用完全公平調度算法，引入虛擬運行時間的概念。
- 空閑調度器(idle_sched_class) : 為每個 CPU 都會有一個 idle 線程，當沒有其他進程可以調度時，調度運行idle線程。
進程的調度策略有5種，用戶可以調用調度器里不同的調度策略：
- SCHED_FIFO ：采用了先入先出，不使用時間片的調度算法。若處于可執行狀態，就會一直執行，沒有更高優先級的情況下，進程只能等待其主動讓出 cpu；
- SCHED_RR ：時間片輪轉，進程用完時間片后加入優先級對應的運行隊列的尾部，把 CPU 讓給同一優先級的其他進程；
- SCHED_NORMAL ： 使 task 選擇 CFS 調度器來調度運行；
- SCHED_BATCH：批量處理，使 task 選擇 CFS 調度器來調度運行；
- SCHED_IDLE： 使 task 選擇 CFS 調度器來調度運行
在每個 CPU 中都有一個自身的運行隊列 rq，每個活動進程只出現在一個運行隊列中，在多個 CPU 上同時運行一個進程是不可能的。
運行隊列是使用如下結構實現的：
struct rq {
//運行隊列中進程的數目
unsigned long nr_running;
//進程切換總數
u64 nr_switches;
//用于完全公平調度器的就緒隊列
struct cfs_rq cfs;
//用于實時調度器的就緒隊列
struct rt_rq rt;
//記錄本cpu尚處于TASK_UNINTERRUPTIBLE狀態的進程數，和負載信息有關
unsigned long nr_uninterruptible;
//curr指向當前運行的進程實例，idle 指向空閑進程的實例
struct task_struct *curr, *idle;
//上一次調度時的mm結構
struct mm_struct *prev_mm;
...
};
每個運行隊列中有2個調度隊列：CFS 調度隊列 和 RT 調度隊列。
tast 作為調度實體加入到 CPU 中的調度隊列中。
系統中所有的運行隊列都在 runqueues 數組中，該數組的每個元素分別對應于系統中的一個 CPU。在單處理器系統中，由于只需要一個就緒隊列，因此數組只有一個元素。
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
內核也定義了一下便利的宏，其含義很明顯。
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() (&__get_cpu_var(runqueues))
#define task_rq(p) cpu_rq(task_cpu(p))
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
進程調度與切換
在分析調度流程之前，我們先來看在什么情況下要執行調度程序，我們把這種情況叫做調度時機。
Linux 調度時機主要有。
- 進程狀態轉換的時刻：進程終止、進程睡眠；
- 當前進程的時間片用完時（current->counter=0）；
- 設備驅動程序；
- 進程從中斷、異常及系統調用返回到用戶態時。
時機1，進程要調用 sleep() 或 exit() 等函數進行狀態轉換，這些函數會主動調用調度程序進行進程調度。
時機2，由于進程的時間片是由時鐘中斷來更新的，因此，這種情況和時機4 是一樣的。
時機3，當設備驅動程序執行長而重復的任務時，直接調用調度程序。在每次反復循環中，驅動程序都檢查 need_resched 的值，如果必要，則調用調度程序 schedule() 主動放棄 CPU。
時機4 ， 如前所述， 不管是從中斷、異常還是系統調用返回， 最終都調用 ret_from_sys_call()，由這個函數進行調度標志的檢測，如果必要，則調用調用調度程序。那么，為什么從系統調用返回時要調用調度程序呢？這當然是從效率考慮。從系統調用返回意味著要離開內核態而返回到用戶態，而狀態的轉換要花費一定的時間，因此，在返回到用戶態前，系統把在內核態該處理的事全部做完。
Linux 的調度程序是一個叫 Schedule() 的函數，這個函數來決定是否要進行進程的切換，如果要切換的話，切換到哪個進程等。
Schedule 的實現
asmlinkage void __sched schedule(void)
{
/*prev 表示調度之前的進程, next 表示調度之后的進程 */
struct task_struct *prev, *next;
long *switch_count;
struct rq *rq;
int cpu;
need_resched:
preempt_disable(); //關閉內核搶占
cpu = smp_processor_id(); //獲取所在的cpu
rq = cpu_rq(cpu); //獲取cpu對應的運行隊列
rcu_qsctr_inc(cpu);
prev = rq->curr; /*讓prev 成為當前進程 */
switch_count = &prev->nivcsw;
/釋放全局內核鎖，并開this_cpu 的中斷/
release_kernel_lock(prev);
need_resched_nonpreemptible:
__update_rq_clock(rq); //更新運行隊列的時鐘值
...
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
// 對應到CFS,則為 put_prev_task_fair
prev->sched_class->put_prev_task(rq, prev); //通知調度器類當前運行進程要被另一個進程取代
/pick_next_task以優先級從高到底依次檢查每個調度類，從最高優先級的調度類中選擇最高優先級的進程作為
下一個應執行進程（若其余都睡眠，則只有當前進程可運行，就跳過下面了）/
next = pick_next_task(rq, prev); //選擇需要進行切換的task
//進程prev和進程next切換前更新各自的sched_info
sched_info_switch(prev, next);
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
++switch_count;
//完成進程切換(上下文切換)
context_switch(rq, prev, next); / unlocks the rq */
} else
spin_unlock_irq(&rq->lock);
if (unlikely(reacquire_kernel_lock(current) < 0)) {
cpu = smp_processor_id();
rq = cpu_rq(cpu);
goto need_resched_nonpreemptible;
}
preempt_enable_no_resched();
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
goto need_resched;
}
從代碼分析來看，Schedule 主要完成了2個功能：
- 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; //獲取要執行進程的mm字段
oldmm = prev->active_mm; //被切換出去進程的 active_mm 字段
//mm為空，說明是一個內核線程
if (unlikely(!mm)) {
//內核線程共享上一個運行進程的mm
next->active_mm = oldmm; //借用切換出去進程的 mm_struct
//增加引用計數
atomic_inc(&oldmm->mm_count);
//惰性TLB，因為內核線程沒有虛擬地址空間的用戶空間部分，告訴底層體系結構無須切換
enter_lazy_tlb(oldmm, next);
} else
//進程切換包括進程的執行環境切換和運行空間的切換。運行空間的切換是有switch_mm完成的。若是用戶進程，則切換運行空間
switch_mm(oldmm, mm, next);
//若上一個運行進程是內核線程
if (unlikely(!prev->mm)) {
prev->active_mm = NULL; //斷開內核線程與之前借用的地址空間聯系
//更新運行隊列的prev_mm成員，為之后歸還借用的mm_struct做準備
rq->prev_mm = oldmm;
}
/* Here we just switch the register state and the stack. */
//切換進程的執行環境
switch_to(prev, next, prev);
barrier();
//進程切換之后的處理工作
finish_task_switch(this_rq(), prev);
}
進程上下文切換包括進程的地址空間的切換和執行環境的切換。
- switch_mm 完成了進程的地址空間的切換：如果新進程有自己的用戶空間，也就是說，如果 next->mm 與 next->active_mm 相同，那么，switch_mm() 函數就把該進程從內核空間切換到用戶空間，也就是加載next 的頁目錄。如果新進程無用戶空間（next->mm 為空），也就是說，如果它是一個內核線程，那它就要在內核空間運行，因此，需要借用前一個進程（prev）的地址空間，因為所有進程的內核空間都是共享的，因此，這種借用是有效的。
- switch_to 完成了執行環境的切換，該宏實現了進程之間的真正切換。
//進程切換包括進程的執行環境切換和運行空間的切換。運行空間的切換是有switch_mm完成的
static inline void switch_mm(struct mm_struct *prev,
struct mm_struct *next,
struct task_struct tsk)
{
//得到當前進程運行的cpu
int cpu = smp_processor_id();
//若要切換的prev != next，執行切換過程
if (likely(prev != next)) {
/ stop flush ipis for the previous mm */
//清除prev的cpu_vm_mask，標志prev已經棄用了當前cpu
cpu_clear(cpu, prev->cpu_vm_mask);
#ifdef CONFIG_SMP
//在smp系統中，更新cpu_tlbstate
per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK;
per_cpu(cpu_tlbstate, cpu).active_mm = next;
#endif
//設置cpu_vm_mask，表示next占用的當前的cpu
cpu_set(cpu, next->cpu_vm_mask);
/* Re-load page tables */
//加載CR3
load_cr3(next->pgd);
/*
• load the LDT, if the LDT is different:
*/
//若ldt不相同，還要加載ldt
if (unlikely(prev->context.ldt != next->context.ldt))
load_LDT_nolock(&next->context);
}
#ifdef CONFIG_SMP
else {
per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK;
//prev == next 那當前cpu中的active_mm就是prev，也即是next
BUG_ON(per_cpu(cpu_tlbstate, cpu).active_mm != next);
/*
在smp系統中，雖然mm時一樣的，但需要加載CR3
執行cpu_test_and_set來判斷next是否正運行在此cpu上，這里是判斷在切換next是否運行
在當前的cpu中，
假設cpu為1，一個進程在1上執行時候，被調度出來，再次調度的時候，
又發生在cpu1上
*/
if (!cpu_test_and_set(cpu, next->cpu_vm_mask)) {
/* We were in lazy tlb mode and leave_mm disabled
• tlb flush IPI delivery. We must reload %cr3.
*/
load_cr3(next->pgd);
load_LDT_nolock(&next->context);
}
}
#endif
}
對于 switch_mm 處理，關鍵的一步就是它將新進程頁面目錄的起始物理地址裝入到寄存器 CR3 中。CR3 寄存器總是指向當前進程的頁面目錄。
#define switch_to(prev,next,last) do {
unsigned long esi,edi;
/*分別保存了eflags、ebp、esp，flags和 ebp他們是被保存在prev進程(其實就是要被切換出去的進程)的內核堆棧中的*/
asm volatile("pushflnt" /* Save flags */
"pushl %%ebpnt"
//%0為 prev->thread.esp， %1 為 prev->thread.eip
"movl %%esp,%0nt" /* save ESP */
//%5為 next->thread.esp，%6 為 next->thread.eip
"movl %5,%%espnt" /* restore ESP */
/*將標號為1所在的地址，也即是"popl %%ebpnt" 指令所在的地址保存在prev->thread.eip中，作為prev進程
下一次被調度運行而切入時的返回地址，因此可以知道，每個進程調離時都要執行"movl $1f,%1nt"，所以
這就決定了每個進程在受到調度恢復運行時都會從標號1處也即是"popl %%ebpnt"開始執行。
但是有一個例外，那就是新創建的進程，新創建的進程并沒有在上一次調離時執行上面的指令，所以一來要將其
task_struct中的thread.eip事先設置好，二來所設置的返回地址也未必是這里的標號1所在的地址，這取決于系統空間
堆棧的設置。事實上可以下fork()中可以看到，這個地址在copy_thread()中設置為ret_from_fork,其代碼在entry.S中，
也就是對于新創建的進程，在調用schedule_tail()后直接轉到了ret_from_sys_call, 也即是返回到了用戶空間去了
*/
"movl $1f,%1nt" /* save EIP */
/*將next->thread.eip壓入棧中，這里的next->thread.eip正是next進程上一次被調離在"movl $1f,%1nt"保存的，也即是
指向標號為1的地方，也即是"popl %%ebpnt"指令所在的地址*/
"pushl %6nt" /* restore EIP */
/*需要注意的是 __switch_to 是經過regparm(3)來修飾的，這個是gcc的一個擴展語法。
即從eax，ebx，ecx寄存器取函數的參數。這樣，__switch_to函數的參數就是從寄存器中取的。
并是不向普通函數那樣從堆棧中取的。在__switch_to之前，將next->thread.eip壓棧了，這樣從函數返回后
，它的下一條運行指令就是 next->thread.eip了。
對于新創建的進程。我們設置了p->thread.eip = ret_from_fork.這樣子進程被切換進來之后，就會通過
ret_from_fork返回到用戶空間了。
對于已經運行的進程，我們這里可以看到，在進程被切換出去的時候，prev->thread.eip被設置了標號1的地址，
即是從標號1的地址開始運行的。
標號1的操作:
恢復ebp(popl %%ebp)
恢復flags(popf1)
這樣就恢復了進程的執行環境。
從代碼可以看到，在進程切換時，只保留了flags esp和ebp寄存器，顯示的用到了eax和edx，
那其他寄存器怎么保存的呢?
實際上過程切換只是發生在內核態，對于內核態的寄存器來說，它的段寄存器都是一樣的，所以不需要保存
*/
/*通過jmp指令轉入到函數__switch_to中，由于上一行"pushl %6nt"把next->thread.eip，也即是標號為1的地址壓到棧中，所以
跳入__switch_to執行完后，執行標記為1的地方，也即是"popl %%ebpnt" 指令*/
"jmp __switch_ton"
"1:t"
"popl %%ebpnt"
"popfl"
:"=m" (prev->thread.esp),"=m" (prev->thread.eip),
"=a" (last),"=S" (esi),"=D" (edi)
:"m" (next->thread.esp),"m" (next->thread.eip),
"2" (prev), "d" (next));
} while (0)
switch_to 把寄存器中的值比如esp等存放到進程thread結構中，保存現場一邊后續恢復，同時調用 __switch_to 完成了堆棧的切換。
在進程的 task_struct 結構中有個重要的成分 thread，它本身是一個數據結構 thread_struct, 里面記錄著進程在切換時的（系統空間）堆棧指針，取指令地址（也就是“返回地址”）等關鍵性的信息。
/*
__switch_to 處理的主要邏輯是TSS,其核心就是load_esp0將TSS中的內核空間(0級)堆棧指針換成next->esp0. 這是因為
cpu在穿越中斷門或者陷阱門時要根據新的運行級別從TSS中取得進程在系統空間的堆棧指針，其次，段寄存器fs和gs的內容也做了
相應的切換。同時cpu中為debug而設計的一些寄存器以及說明進程I/O 操作權限的位圖。
*/
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
struct thread_struct *prev = &prev_p->thread,
*next = &next_p->thread;
int cpu = smp_processor_id();
struct tss_struct *tss = &per_cpu(init_tss, cpu);
...
/* 將TSS 中的內核級（0 級）堆棧指針換成next->esp0，這就是next 進程在內核棧的指針*/
load_esp0(tss, next);
//為prev保存gs
savesegment(gs, prev->gs);
//從next的tls_array緩存中加載線程的Thread-Local Storage描述符
load_TLS(next, cpu);
/*若當前特權級別是0且prev->iopl != next->iopl，則恢復IOPL設置set_iopl_mask
*/
if (get_kernel_rpl() && unlikely(prev->iopl != next->iopl))
set_iopl_mask(next->iopl);
/*根據thread_info的TIF標志_TIF_WORK_CTXSW_PREV和 _TIF_WORK_CTXSW_NEXT 判斷是否需要處理
debug寄存器和IO位圖*/
if (unlikely(task_thread_info(prev_p)->flags & _TIF_WORK_CTXSW_PREV ||
task_thread_info(next_p)->flags & _TIF_WORK_CTXSW_NEXT))
__switch_to_xtra(prev_p, next_p, tss);
//設置cpu的lazy模式
arch_leave_lazy_cpu_mode();
//若fpu_counter > 5 則恢復next_p 的FPU寄存器
if (next_p->fpu_counter > 5)
math_state_restore();
//若需要，恢復gs寄存器
if (prev->gs | next->gs)
loadsegment(gs, next->gs);
x86_write_percpu(current_task, next_p);
return prev_p;
}
關于__switch_to 的工作就是處理 TSS （任務狀態段）。
TSS 全稱task state segment，是指在操作系統進程管理的過程中，任務（進程）切換時的任務現場信息。
linux 為每一個 CPU 提供一個 TSS 段，并且在 TR 寄存器中保存該段。
linux 中之所以為每一個 CPU 提供一個 TSS 段，而不是為每個進程提供一個TSS 段，主要原因是 TR 寄存器永遠指向它，在任務切換的適合不必切換 TR 寄存器，從而減小開銷。
在從用戶態切換到內核態時，可以通過獲取 TSS 段中的 esp0 來獲取當前進程的內核棧 棧頂指針，從而可以保存用戶態的 cs,esp,eip 等上下文。
TSS 在任務切換過程中起著重要作用，通過它實現任務的掛起和恢復。所謂任務切換是指，掛起當前正在執行的任務，恢復或啟動另一任務的執行。
在任務切換過程中，首先，處理器中各寄存器的當前值被自動保存到 TR（任務寄存器）所指定的任務的 TSS 中；然后，下一任務的 TSS 被裝入 TR；最后，從 TR 所指定的 TSS 中取出各寄存器的值送到處理器的各寄存器中。由此可見，通過在 TSS 中保存任務現場各寄存器狀態的完整映象，實現任務的切換。
因此，__switch_to 核心內容就是將 TSS 中的內核空間（0級）堆棧指針換成 next->esp0。這是因為 CPU 在穿越中斷門或者陷阱門時要根據新的運行級別從TSS中取得進程在系統空間的堆棧指針。
thread_struct.esp0 指向進程的系統空間堆棧的頂端。當一個進程被調度運行時，內核會將這個變量寫入 TSS 的 esp0 字段，表示這個進程進入0級運行時其堆棧的位置。換句話說，進程的 thread_struct 結構中的 esp0 保存著其系統空間堆棧指針。當進程穿過中斷門、陷阱門或者調用門進入系統空間時，處理器會從這里恢復期系統空間棧。
由于棧中變量的訪問依賴的是段、頁、和 esp、ebp 等這些寄存器，所以當段、頁、寄存器切換完以后，棧中的變量就可以被訪問了。
因此 switch_to 完成了進程堆棧的切換，由于被切進的進程各個寄存器的信息已完成切換，因此 next 進程得以執行指令運行。
由于 A 進程在調用 switch_to 完成了與 B 進程堆棧的切換，也即是寄存器中的值都是 B 的，所以 A 進程在 switch_to 執行完后，A停止運行，B開始運行，當過一段時間又把 A 進程切進去后，A 開始從 switch_to 后面的代碼開始執行。
schedule 的調用流程如下：
