【摘要】本文簡(jiǎn)單介紹了任務(wù)的各種狀態(tài)和PCB的結(jié)構(gòu)，分析了幾種任務(wù)調(diào)度策略，詳解了schedule，并分析了如何進(jìn)行進(jìn)程上下文切換；隨后分析了2.6內(nèi)核如何優(yōu)化了任務(wù)調(diào)度算法；最后介紹了內(nèi)核定時(shí)器的實(shí)現(xiàn)機(jī)制和系統(tǒng)調(diào)用的實(shí)現(xiàn)過(guò)程。
【關(guān)鍵詞】進(jìn)程控制塊PCB，RR，FIFO，內(nèi)核調(diào)度算法，任務(wù)切換，內(nèi)核定時(shí)，timer，軟中斷softirq，系統(tǒng)調(diào)用
一、2.6版以前內(nèi)核進(jìn)程調(diào)度機(jī)制簡(jiǎn)介... 1
1、進(jìn)程控制塊數(shù)據(jù)結(jié)構(gòu)... 1
2、進(jìn)程調(diào)度... 2
3、進(jìn)程上下文切換... 5
二、2.6版內(nèi)核對(duì)進(jìn)程調(diào)度的優(yōu)化... 7
1、新調(diào)度算法簡(jiǎn)介... 7
2、2.6版新調(diào)度算法分析... 8
3、2.6版新調(diào)度算法流程圖... 11
三、內(nèi)核中斷及定時(shí)器實(shí)現(xiàn)分析... 11
四、系統(tǒng)調(diào)用的實(shí)現(xiàn)過(guò)程... 14
參考資料：... 14
一、2.6版以前內(nèi)核進(jìn)程調(diào)度機(jī)制簡(jiǎn)介
Linux的進(jìn)程管理由進(jìn)程控制塊、進(jìn)程調(diào)度、中斷處理、任務(wù)隊(duì)列、定時(shí)器、bottom half隊(duì)列、系統(tǒng)調(diào)用、進(jìn)程通信等等部分組成。
進(jìn)程調(diào)用分為實(shí)時(shí)進(jìn)程調(diào)度和非實(shí)時(shí)進(jìn)程調(diào)度兩種。前者調(diào)度時(shí)，可以采用基于動(dòng)態(tài)優(yōu)先級(jí)的輪轉(zhuǎn)法（RR），也可以采用先進(jìn)先出算法（FIFO）。后者調(diào)度時(shí)，一律采用基于動(dòng)態(tài)優(yōu)先級(jí)的輪轉(zhuǎn)法。某個(gè)進(jìn)程采用何種調(diào)度算法由該進(jìn)程的進(jìn)程控制塊中的某些屬性決定，沒(méi)有專門(mén)的系統(tǒng)用來(lái)處理關(guān)于進(jìn)程調(diào)度的相關(guān)事宜。Linux的進(jìn)程調(diào)度由schedule( )函數(shù)負(fù)責(zé)，任何進(jìn)程，當(dāng)它從系統(tǒng)調(diào)用返回時(shí)，都會(huì)轉(zhuǎn)入schedule( )，而中斷處理函數(shù)完成它們的響應(yīng)任務(wù)以后，也會(huì)進(jìn)入schedule( )。
1、進(jìn)程控制塊數(shù)據(jù)結(jié)構(gòu)
Linux系統(tǒng)的進(jìn)程控制塊用數(shù)據(jù)結(jié)構(gòu)task_struct表示，這個(gè)數(shù)據(jù)結(jié)構(gòu)占用1680個(gè)字節(jié)，具體的內(nèi)容不在這里介紹，詳細(xì)內(nèi)容見(jiàn)《Linux內(nèi)核2.4版源代碼分析大全》第二頁(yè)。
進(jìn)程的狀態(tài)主要包括如下幾個(gè)：
TASK_RUNNING 正在運(yùn)行或在就緒隊(duì)列run-queue中準(zhǔn)備運(yùn)行的進(jìn)程，實(shí)際參與進(jìn)程調(diào)度。
TASK_INTERRUPTIBLE 處于等待隊(duì)列中的進(jìn)程，待資源有效時(shí)喚醒，也可由其它進(jìn)程通過(guò)信號(hào)或定時(shí)中斷喚醒后進(jìn)入就緒隊(duì)列run-queue。
TASK_UNINTERRUPTIBLE 處于等待隊(duì)列的進(jìn)程，待資源有效時(shí)喚醒，不可由其它進(jìn)程通過(guò)信號(hào)或者定時(shí)中斷喚醒。
TASK_ZOMBIE 表示進(jìn)程結(jié)束但尚未消亡的一種狀態(tài)（僵死），此時(shí)，進(jìn)程已經(jīng)結(jié)束運(yùn)行并且已經(jīng)釋放了大部分資源，但是尚未釋放進(jìn)程控制塊。
TASK_STOPPED 進(jìn)程暫停，通過(guò)其它進(jìn)程的信號(hào)才能喚醒。
所有進(jìn)程（以PCB形式）組成一個(gè)雙向列表。next_task和prev_task就是鏈表的前后向指針。鏈表的頭尾都是init_task（init進(jìn)程）。不過(guò)進(jìn)程還要根據(jù)其進(jìn)程ID號(hào)插入到一個(gè)hash表當(dāng)中，目的是加快進(jìn)程搜索速度。
2、進(jìn)程調(diào)度
Linux進(jìn)程調(diào)度由schedule( )執(zhí)行，其任務(wù)是在run-queue隊(duì)列中選出一個(gè)就緒進(jìn)程。
每個(gè)進(jìn)程都有一個(gè)調(diào)度策略，在它的task_struct中規(guī)定（policy屬性），或?yàn)?/span>SCHED_RR,SCHED_FIFO，或?yàn)?/span>SCHED_OTHER。前兩種為實(shí)時(shí)進(jìn)程調(diào)度策略，后一種為普通進(jìn)程調(diào)度策略。
用戶進(jìn)程由do_fork( )函數(shù)創(chuàng)建，它也是fork系統(tǒng)調(diào)用的執(zhí)行者。do_fork( )創(chuàng)建一個(gè)新的進(jìn)程，繼承父進(jìn)程的現(xiàn)有資源，初始化進(jìn)程時(shí)鐘、信號(hào)、時(shí)間等數(shù)據(jù)。完成子進(jìn)程的初始化后，父進(jìn)程將它掛到就緒隊(duì)列，返回子進(jìn)程的pid。進(jìn)程創(chuàng)建時(shí)的狀態(tài)為TASK_UNINTERRUPTIBLE，在do_fork( )結(jié)束前被父進(jìn)程喚醒后，變?yōu)?/span>TASK_RUNNING。處于TASK_RUNNING狀態(tài)的進(jìn)程被移到就緒隊(duì)列中，當(dāng)適當(dāng)?shù)臅r(shí)候由schedule( )按CPU調(diào)度算法選中，獲得CPU。
如果進(jìn)程采用輪轉(zhuǎn)法，當(dāng)時(shí)間片到時(shí)（10ms的整數(shù)倍），由時(shí)鐘中斷觸發(fā)timer_interrupt( )函數(shù)引起新一輪的調(diào)度，把當(dāng)前進(jìn)程掛到就緒隊(duì)列的尾部。獲得CPU而正在運(yùn)行的進(jìn)程若申請(qǐng)不到某個(gè)資源，則調(diào)用sleep_on( )或interruptible_sleep_on( )睡眠，并進(jìn)入就緒隊(duì)列尾。狀態(tài)為TASK_INTERRUPTIBLE的睡眠進(jìn)程當(dāng)它申請(qǐng)的資源有效時(shí)被喚醒，也可以由信號(hào)或者定時(shí)中斷喚醒，喚醒以后進(jìn)程狀態(tài)變?yōu)?/span>TASK_RUNNING，并進(jìn)入就緒隊(duì)列。
首先介紹一下2.6版以前的的調(diào)度算法的主要思想，下面的schedule( )函數(shù)是內(nèi)核2.4.23中摘錄的：
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this_cpu, c;
spin_lock_prefetch(&runqueue_lock);
BUG_ON(!current->active_mm);
need_resched_back:
/*記錄當(dāng)前進(jìn)程和處理此進(jìn)程的CPU號(hào)*/
prev = current;
this_cpu = prev->processor;
/*判斷是否處在中斷當(dāng)中，這里不允許在中斷處理當(dāng)中調(diào)用sechedule( )*/
if (unlikely(in_interrupt( ))) {
printk("Scheduling in interrupt\n");
BUG( );
}
release_kernel_lock(prev, this_cpu);
/*'sched_data' 是受到保護(hù)的，每個(gè)CPU只能運(yùn)行一個(gè)進(jìn)程。*/
sched_data = & aligned_data[this_cpu].schedule_data;
spin_lock_irq(&runqueue_lock);
/*如果當(dāng)前進(jìn)程的調(diào)度策略是輪轉(zhuǎn)RR，那么需要判斷當(dāng)前進(jìn)程的時(shí)間片是否已經(jīng)用完，如果已經(jīng)用完，則重新計(jì)算時(shí)間片值，然后將該進(jìn)程掛接到就緒隊(duì)列run-queue的最后*/
if (unlikely(prev->policy == SCHED_RR))
if (!prev->counter) {
prev->counter = NICE_TO_TICKS(prev->nice);
move_last_runqueue(prev);
}
/*假如進(jìn)程為TASK_INTERRUPTTIBLE狀態(tài)，則將其狀態(tài)置為TASK_RUNNING。如是其它狀態(tài)，則將該進(jìn)程轉(zhuǎn)為睡眠狀態(tài)，從運(yùn)行隊(duì)列中刪除。（已不具備運(yùn)行的條件） */
switch (prev->state) {
case TASK_INTERRUPTIBLE:
if (signal_pending(prev)) {
prev->state = TASK_RUNNING;
break;
}
default:
del_from_runqueue(prev);
case TASK_RUNNING:;
}
/*當(dāng)前進(jìn)程不需要重新調(diào)度*/
prev->need_resched = 0;
/*下面是一般的進(jìn)程調(diào)度過(guò)程*/
repeat_schedule:
next = idle_task(this_cpu);
c = -1000;
/*遍歷進(jìn)程就緒隊(duì)列，如果該進(jìn)程能夠進(jìn)行調(diào)度（對(duì)于SMP來(lái)說(shuō)就是判斷當(dāng)前CPU未被占用能夠執(zhí)行這個(gè)進(jìn)程，對(duì)于非SMP系統(tǒng)則為1），則計(jì)算該進(jìn)程的優(yōu)先級(jí)，如果優(yōu)先級(jí)大于當(dāng)前進(jìn)程，則next指針指向新的進(jìn)程，循環(huán)直到找到優(yōu)先級(jí)最大的那個(gè)進(jìn)程*/
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p, this_cpu)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
/* 判斷是否需要重新計(jì)算每個(gè)進(jìn)程的時(shí)間片，判斷的依據(jù)是所有正準(zhǔn)備進(jìn)行調(diào)度的進(jìn)程時(shí)間片耗盡，這時(shí)，就需要對(duì)就緒隊(duì)列中的每一個(gè)進(jìn)程都重新計(jì)算時(shí)間片，然后返回前面的調(diào)度過(guò)程，重新在就緒隊(duì)列當(dāng)中查找優(yōu)先級(jí)最高的進(jìn)程執(zhí)行調(diào)度。 */
if (unlikely(!c)) {
struct task_struct *p;
spin_unlock_irq(&runqueue_lock);
read_lock(&tasklist_lock);
for_each_task(p)
p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
read_unlock(&tasklist_lock);
spin_lock_irq(&runqueue_lock);
goto repeat_schedule;
}
/*CPU私有調(diào)度數(shù)據(jù)中記錄當(dāng)前進(jìn)程的指針，并且將當(dāng)前進(jìn)程與CPU綁定，如果待調(diào)度進(jìn)程與前面一個(gè)進(jìn)程屬于同一個(gè)進(jìn)程，則不需要調(diào)度，直接返回。*/
sched_data->curr = next;
task_set_cpu(next, this_cpu);
spin_unlock_irq(&runqueue_lock);
if (unlikely(prev == next)) {
/* We won't go through the normal tail, so do this by hand */
prev->policy &= ~SCHED_YIELD;
goto same_process;
}
/*全局統(tǒng)計(jì)進(jìn)程上下文切換次數(shù)*/
kstat.context_swtch++;
/*如果后進(jìn)程的mm為0 （未分配頁(yè)），則檢查是否被在被激活的頁(yè)里（active_mm）,否則換頁(yè)。令后進(jìn)程記錄前進(jìn)程激活頁(yè)的信息，將前進(jìn)程的active_mm中的mm_count值加一。將cpu_tlbstate[cpu].state改為 TLBSTATE_LAZY(采用lazy模式) 如果后進(jìn)程的mm不為0（已分配頁(yè)），但尚未激活，換頁(yè)。切換mm（switch_mm）。 如果前進(jìn)程的mm 為0（已失效） ，將其激活記錄置空，將mm結(jié)構(gòu)引用數(shù)減一,刪除該頁(yè)。 */
prepare_to_switch( );
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if (!mm) {
BUG_ON(next->active_mm);
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next, this_cpu);
} else {
BUG_ON(next->active_mm != mm);
switch_mm(oldmm, mm, next, this_cpu);
}
if (!prev->mm) {
prev->active_mm = NULL;
mmdrop(oldmm);
}
}
/*切換到后進(jìn)程，調(diào)度過(guò)程結(jié)束*/
switch_to(prev, next, prev);
__schedule_tail(prev);
same_process:
reacquire_kernel_lock(current);
if (current->need_resched)
goto need_resched_back;
return;
}
3、進(jìn)程上下文切換
首先進(jìn)程切換需要做什么？它做的事只是保留正在運(yùn)行進(jìn)程的"環(huán)境"，并把將要運(yùn)行的進(jìn)程的"環(huán)境"加載上來(lái)，這個(gè)環(huán)境也叫上下文。它包括各個(gè)進(jìn)程"公用"的東西，比如寄存器。
下一個(gè)問(wèn)題，舊的進(jìn)程環(huán)境保存在那，新的進(jìn)程環(huán)境從那來(lái)，在i386上，有個(gè)tss段，是專用來(lái)保存進(jìn)程運(yùn)行環(huán)境的。在Linux來(lái)說(shuō)，在結(jié)構(gòu)task_struct中有個(gè)類型為struct thread_struct的成員叫tss，如下：
struct task_struct {
。。。
/* tss for this task */
struct thread_struct tss;
。。。
};
它是專用來(lái)存放進(jìn)程環(huán)境的，這個(gè)結(jié)構(gòu)體因CPU而異，你看它就能知道有那些寄存器是需要保存的了。 最后的問(wèn)題就是切換了，雖然在i386上CPU可以自動(dòng)根據(jù)tss去進(jìn)行上下文的切換，但是Linux的程序員們更愿意自己做它，原因是這樣能得到更有效的控制，而且作者說(shuō)這和硬件切換的速度差不多，這可是真的夠偉大的。
好了，現(xiàn)在來(lái)看源碼，進(jìn)程切換是使用switch_to這個(gè)宏來(lái)做的,當(dāng)進(jìn)入時(shí)prev即是現(xiàn)在運(yùn)行的進(jìn)程，next是接下來(lái)要切換到的進(jìn)程，
#define switch_to(prev,next,last) do { \
asm volatile(
"pushl %%esi\n\t" \
"pushl %%edi\n\t" \
"pushl %%ebp\n\t" \
// 首先它切換堆棧指針，prev->tss.esp = %esp；%esp = next->tss.esp，這以后的堆棧已經(jīng)是next的堆棧了。
"movl %%esp,%0\n\t" /* save ESP */ \
"movl %3,%%esp\n\t" /* restore ESP */ \
// 然后使進(jìn)程prev的指針保存為標(biāo)號(hào)為1的那一個(gè)指針，這樣下次進(jìn)程prev可以運(yùn)行時(shí)，它第一個(gè)執(zhí)行的就是pop指令。
"movl $1f,%1\n\t" /* save EIP */ \
// 把進(jìn)程next保存的指針推進(jìn)堆棧中，這句作用是，從__switch_to返回時(shí)，下一個(gè)要執(zhí)行的指令將會(huì)是這個(gè)指針?biāo)赶虻闹噶盍恕?/span>
"pushl %4\n\t" /* restore EIP */ \
// 使用jump跳到__switch_to函數(shù)的結(jié)果是：調(diào)用switch_to函數(shù)但不象call那樣要壓棧，但是ret返回時(shí)，仍是要彈出堆棧的，也就是上條指令中推進(jìn)去的指令指針。這樣，堆棧和指令都換了，進(jìn)程也就被"切換"了。
"jmp __switch_to\n" \
// 由于上面所說(shuō)的原因，__switch_to返回后并不會(huì)執(zhí)行下面的語(yǔ)句，要執(zhí)行到這，只有等進(jìn)程prev重新被調(diào)度了。
"1:\t" \
"popl %%ebp\n\t" \
"popl %%edi\n\t" \
"popl %%esi\n\t" \
:"=m" (prev->tss.esp),"=m" (prev->tss.eip), \
"=b" (last) \
:"m" (next->tss.esp),"m" (next->tss.eip), \
"a" (prev), "d" (next), \
"b" (prev)); \
} while (0)
最后是__switch_to函數(shù)，它雖然是c形式，但內(nèi)容還都是嵌入?yún)R編。
// 這句可能需要你去記起前面第二章中所描述的gdt表的結(jié)構(gòu)了，它的作用是把進(jìn)程next的tss描述符的type中的第二位清0，這位表示這個(gè)描述符是不是當(dāng)前正在用的描述符，作者說(shuō)如果不清0就把它load進(jìn)tss段寄存器的話，系統(tǒng)會(huì)報(bào)異常（我可沒(méi)試過(guò)）。
gdt_table[next->tss.tr >> 3].b &= 0xfffffdff;
// 把進(jìn)程next的tss段load到tss段存器中。
asm volatile("ltr %0": :"g" (*(unsigned short *)&next->tss.tr));
// 保存進(jìn)程prev的fs和gs段寄存器
asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->tss.fs));
asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->tss.gs));
然后下面就是load進(jìn)程next的ldt，頁(yè)表，fs，gs，debug寄存器。
因?yàn)?/span>Linux一般并不使用ldt，所以它們一般會(huì)指向一個(gè)共同的空的ldt段描述符，這樣就可能不需要切換ldt了，如果進(jìn)程next和prev是共享內(nèi)存的話，那么頁(yè)表的轉(zhuǎn)換也就不必要了（這一般發(fā)生在clone時(shí)）。
二、2.6版內(nèi)核對(duì)進(jìn)程調(diào)度的優(yōu)化
1、新調(diào)度算法簡(jiǎn)介
2.6版本的Linux內(nèi)核使用了新的調(diào)度器算法，稱為O（1）算法，它在高負(fù)載的情況下執(zhí)行得非常出色，并在有多個(gè)處理器時(shí)能夠很好地?cái)U(kuò)展。 2.4版本的調(diào)度器中，時(shí)間片重算算法要求在所有的進(jìn)程都用盡它們的時(shí)間片后，新時(shí)間片才會(huì)被重新計(jì)算。在一個(gè)多處理器系統(tǒng)中，當(dāng)進(jìn)程用完它們的時(shí)間片后不得不等待重算，以得到新的時(shí)間片，從而導(dǎo)致大部分處理器處于空閑狀態(tài)，影響SMP的效率。此外，當(dāng)空閑處理器開(kāi)始執(zhí)行那些時(shí)間片尚未用盡的、處于等待狀態(tài)的進(jìn)程時(shí)，會(huì)導(dǎo)致進(jìn)程開(kāi)始在處理器之間“跳躍”。當(dāng)一個(gè)高優(yōu)先級(jí)進(jìn)程或交互式進(jìn)程發(fā)生跳躍時(shí)，整個(gè)系統(tǒng)的性能就會(huì)受到影響。
新調(diào)度器解決上述問(wèn)題的方法是，基于每個(gè)CPU來(lái)分布時(shí)間片，并取消全局同步和重算循環(huán)。調(diào)度器使用了兩個(gè)優(yōu)先級(jí)數(shù)組，即活動(dòng)數(shù)組和過(guò)期數(shù)組，可以通過(guò)指針來(lái)訪問(wèn)它們。活動(dòng)數(shù)組中包含所有映射到某個(gè)CPU且時(shí)間片尚未用盡的任務(wù)。過(guò)期數(shù)組中包含時(shí)間片已經(jīng)用盡的所有任務(wù)的有序列表。如果所有活動(dòng)任務(wù)的時(shí)間片都已用盡，那么指向這兩個(gè)數(shù)組的指針互換，包含準(zhǔn)備運(yùn)行任務(wù)的過(guò)期數(shù)組成為活動(dòng)數(shù)組，而空的活動(dòng)數(shù)組成為包含過(guò)期任務(wù)的新數(shù)組。數(shù)組的索引存儲(chǔ)在一個(gè)64位的位圖中，所以很容易找到最高優(yōu)先級(jí)的任務(wù)。
新調(diào)度器的主要優(yōu)點(diǎn)包括：
◆ SMP效率 如果有工作需要完成，所有處理器都會(huì)工作。
◆ 等待進(jìn)程 沒(méi)有進(jìn)程需要長(zhǎng)時(shí)間地等待處理器，也沒(méi)有進(jìn)程會(huì)無(wú)端地占用大量的CPU時(shí)間。
◆ SMP進(jìn)程映射 進(jìn)程只映射到一個(gè)CPU，而且不會(huì)在CPU之間跳躍。
◆ 優(yōu)先級(jí) 非重要任務(wù)的優(yōu)先級(jí)低，反之亦然。
◆ 負(fù)載平衡 調(diào)度器會(huì)降低那些超出處理器負(fù)載能力的進(jìn)程的優(yōu)先級(jí)。
◆ 交互性能 即使在高負(fù)載的情況下，系統(tǒng)花費(fèi)很長(zhǎng)時(shí)間來(lái)響應(yīng)鼠標(biāo)點(diǎn)擊或鍵盤(pán)輸入的情況也不會(huì)再發(fā)生。
2.6版內(nèi)核中，進(jìn)程調(diào)度經(jīng)過(guò)重新編寫(xiě)，調(diào)度程序不需每次都掃描所有的任務(wù)，而是在一個(gè)任務(wù)變成就緒狀態(tài)時(shí)將其放到一個(gè)名為“當(dāng)前”的隊(duì)列中。當(dāng)進(jìn)程調(diào)度程序運(yùn)行時(shí)，只選擇隊(duì)列中最有利的任務(wù)來(lái)執(zhí)行。這樣，調(diào)度可以在一個(gè)恒定的時(shí)間里完成。當(dāng)任務(wù)執(zhí)行時(shí)，它會(huì)得到一個(gè)時(shí)間段，或者在其轉(zhuǎn)到另一線程之前得到一段時(shí)間的處理器使用權(quán)。當(dāng)時(shí)間段用完后，任務(wù)會(huì)被轉(zhuǎn)移到另一個(gè)名為“過(guò)期”的隊(duì)列中。在該隊(duì)列中，任務(wù)會(huì)根據(jù)其優(yōu)先級(jí)進(jìn)行排序。
從某種意義上說(shuō)，所有位于“當(dāng)前”隊(duì)列的任務(wù)都將被執(zhí)行，并被轉(zhuǎn)移到“過(guò)期”隊(duì)列中。當(dāng)這種事情發(fā)生時(shí)，隊(duì)列就會(huì)進(jìn)行切換，原來(lái)的“過(guò)期”隊(duì)列成為“當(dāng)前”隊(duì)列，而空的“當(dāng)前”隊(duì)列則變成“過(guò)期”隊(duì)列。由于在新的“當(dāng)前”隊(duì)列中，任務(wù)已經(jīng)被排列好，調(diào)度程序現(xiàn)在使用簡(jiǎn)單的隊(duì)列算法，即總是取當(dāng)前隊(duì)列的第一個(gè)任務(wù)進(jìn)行執(zhí)行。這個(gè)新過(guò)程要比老過(guò)程快得多。
2、2.6版新調(diào)度算法分析
下面的schedule( )函數(shù)摘錄自2.6.6版內(nèi)核源碼：
asmlinkage void __sched schedule(void)
{
long *switch_count;
task_t *prev, *next;
runqueue_t *rq;
prio_array_t *array;
struct list_head *queue;
unsigned long long now;
unsigned long run_time;
int idx;
if (likely(!(current->state & (TASK_DEAD | TASK_ZOMBIE)))) {
if (unlikely(in_atomic( ))) {
printk(KERN_ERR "bad: scheduling while atomic!\n");
dump_stack( );
}
}
need_resched:
preempt_disable( );
prev = current;
/*獲取相應(yīng)CPU的進(jìn)程就緒隊(duì)列，每一個(gè)CPU都會(huì)有一個(gè)進(jìn)程就緒等待隊(duì)列，每個(gè)等待隊(duì)列包括兩個(gè)優(yōu)先級(jí)數(shù)組，活動(dòng)數(shù)組和過(guò)期數(shù)組，兩個(gè)數(shù)組可以進(jìn)行輪換。CPU相關(guān)等待隊(duì)列run-queue的數(shù)據(jù)結(jié)構(gòu)定義如下：
struct runqueue {
spinlock_t lock; /*隊(duì)列自旋鎖*/
unsigned long long nr_switches;/*進(jìn)程上下文切換次數(shù)計(jì)數(shù)器*/
unsigned long nr_running, expired_timestamp, nr_uninterruptible,
timestamp_last_tick;
task_t *curr, *idle; /*標(biāo)記當(dāng)前CPU正在執(zhí)行的任務(wù)及空閑任務(wù)的PCB指針*/
struct mm_struct *prev_mm; /*內(nèi)存數(shù)據(jù)結(jié)構(gòu)*/
prio_array_t *active, *expired, arrays[2]; /*優(yōu)先級(jí)活動(dòng)和過(guò)期數(shù)組，活動(dòng)數(shù)組用來(lái)標(biāo)記當(dāng)前時(shí)間片未用完并且處于等待調(diào)度狀態(tài)的進(jìn)程列表，而過(guò)期數(shù)組用來(lái)標(biāo)記當(dāng)前時(shí)間片消耗完畢，無(wú)法繼續(xù)運(yùn)行的進(jìn)程列表*/
int best_expired_prio, prev_cpu_load[NR_CPUS];
task_t *migration_thread;
struct list_head migration_queue;
atomic_t nr_iowait;
}*/
rq = this_rq( );
release_kernel_lock(prev);
now = sched_clock( );
if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
run_time = now - prev->timestamp;
else
run_time = NS_MAX_SLEEP_AVG;
/*
* Tasks with interactive credits get charged less run_time
* at high sleep_avg to delay them losing their interactive
* status
*/
if (HIGH_CREDIT(prev))
run_time /= (CURRENT_BONUS(prev) ? : 1);
spin_lock_irq(&rq->lock);
/*
* if entering off of a kernel preemption go straight
* to picking the next task.
*/
switch_count = &prev->nivcsw;
if (prev->state && !(preempt_count( ) & PREEMPT_ACTIVE)) {
switch_count = &prev->nvcsw;
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
unlikely(signal_pending(prev))))
prev->state = TASK_RUNNING;
else
deactivate_task(prev, rq);
}
/*如果當(dāng)前就緒隊(duì)列中沒(méi)有正在運(yùn)行的任務(wù)，則進(jìn)行進(jìn)程上下文切換，到空閑進(jìn)程*/
if (unlikely(!rq->nr_running)) {
#ifdef CONFIG_SMP
load_balance(rq, 1, cpu_to_node_mask(smp_processor_id( )));
#endif
if (!rq->nr_running) {
next = rq->idle;
rq->expired_timestamp = 0;
goto switch_tasks;
}
}
/*獲取當(dāng)前活動(dòng)數(shù)組指針，判斷處于活動(dòng)狀態(tài)的進(jìn)程數(shù)目，如果活動(dòng)數(shù)組當(dāng)中已經(jīng)沒(méi)有任何活動(dòng)的進(jìn)程，則需要將活動(dòng)數(shù)組與過(guò)期數(shù)組進(jìn)行對(duì)換，這樣就可以很快的開(kāi)始新一輪的調(diào)度，這里array指針總是指向活動(dòng)數(shù)組。*/
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
}
/*由于調(diào)度器事先將活動(dòng)數(shù)組的索引存放在了一個(gè)64位的bitmap位圖結(jié)構(gòu)當(dāng)中，排序的依據(jù)是根據(jù)每個(gè)進(jìn)程的優(yōu)先級(jí)排列的，所以當(dāng)我們需要查找當(dāng)前活動(dòng)數(shù)組中優(yōu)先級(jí)最高的進(jìn)程的索引時(shí)，僅僅需要從位圖中找到最前面的一個(gè)索引值就可以了，而不需要象2.4內(nèi)核那樣每次遍歷就緒隊(duì)列，計(jì)算每個(gè)進(jìn)程的優(yōu)先級(jí)然后才能確定應(yīng)該選擇哪個(gè)進(jìn)程作為下一個(gè)調(diào)度的對(duì)象。
查找到當(dāng)前隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程索引，然后在列表中找到相應(yīng)的進(jìn)程。*/
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
/*一個(gè)進(jìn)程的優(yōu)先級(jí)是從0到MAX_PRIO-1（MAX_PRIO為140），實(shí)時(shí)進(jìn)程優(yōu)先級(jí)是從0到MAX_RT_PRIO-1（MAX_RT_PRIO為100），SCHED_NORMAL任務(wù)的優(yōu)先級(jí)在MAX_RT_PRIO到MAX_PRIO-1之間，優(yōu)先級(jí)值越小表明優(yōu)先級(jí)越大。
在這里首先判斷當(dāng)前需要調(diào)度的進(jìn)程是否為實(shí)時(shí)進(jìn)程，如果不是看是不是處于活動(dòng)狀態(tài)，如果是，根據(jù)其消耗的時(shí)間片，重新計(jì)算優(yōu)先級(jí)。*/
if (!rt_task(next) && next->activated > 0) {
unsigned long long delta = now - next->timestamp;
if (next->activated == 1)
delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
array = next->array;
dequeue_task(next, array);
recalc_task_prio(next, next->timestamp + delta);
enqueue_task(next, array);
}
next->activated = 0;
/*開(kāi)始進(jìn)行進(jìn)程切換，關(guān)于內(nèi)核如何進(jìn)行上下文切換這里就不看了*/
switch_tasks:
reacquire_kernel_lock(current);
preempt_enable_no_resched( );
if (test_thread_flag(TIF_NEED_RESCHED))
goto need_resched;
}
3、2.6版新調(diào)度算法流程圖
定時(shí)器是Linux提供的一種定時(shí)服務(wù)的機(jī)制。它在某個(gè)特定的時(shí)間喚醒某個(gè)進(jìn)程，來(lái)做一些工作。Linux初始化時(shí)，init_IRQ( )函數(shù)設(shè)定8253的定時(shí)周期為10ms（一個(gè)tick值）。同樣，在初始化時(shí)，time_init( )用setup_irq( )設(shè)置時(shí)間中斷向量irq0，中斷服務(wù)程序?yàn)?/span>timer_interrupt。
在2.4版內(nèi)核及較早的版本當(dāng)中，定時(shí)器的中斷處理采用底半部機(jī)制，底半處理函數(shù)的注冊(cè)在start_kernel( )函數(shù)中調(diào)用sechd_init( )，在這個(gè)函數(shù)中又調(diào)用init_bh(TIMER_BH, timer_bh)注冊(cè)了定時(shí)器的底半處理函數(shù)。然后系統(tǒng)才調(diào)用time_init( )來(lái)注冊(cè)定時(shí)器的中斷向量和中斷處理函數(shù)。
在中斷處理函數(shù)timer_interrupt( )中，主要是調(diào)用do_timer( )函數(shù)完成工作。do_timer( )函數(shù)的主要功能就是調(diào)用mark_bh( )產(chǎn)生軟中斷，隨后處理器會(huì)在合適的時(shí)候調(diào)用定時(shí)器底半處理函數(shù)timer_bh( )。在timer_bh( )中，實(shí)現(xiàn)了更新定時(shí)器的功能。2.4.23版的do_timer( )函數(shù)代碼如下（經(jīng)過(guò)簡(jiǎn)略）：
void do_timer(struct pt_regs *regs)
{
(*(unsigned long *)&jiffies)++;
update_process_times(user_mode(regs));
mark_bh(TIMER_BH);
}
而在內(nèi)核2.6版本以后，定時(shí)器中斷處理采用了軟中斷機(jī)制而不是底半機(jī)制。時(shí)鐘中斷處理函數(shù)仍然為timer_interrup( )-> do_timer_interrupt( )－> do_timer_interrupt_hook( )－> do_timer( )。不過(guò)do_timer( )函數(shù)的實(shí)現(xiàn)有所不同：
void do_timer(struct pt_regs *regs)
{
jiffies_64++;
update_process_times(user_mode(regs));
update_times( );
}
兩者所調(diào)用的函數(shù)基本相同，但是2.4.23版內(nèi)核與2.6.6內(nèi)核中，對(duì)于update_process_times( )函數(shù)的實(shí)現(xiàn)不同：
void update_process_times(int user_tick)
{
struct task_struct *p = current;
int cpu = smp_processor_id( ), system = user_tick ^ 1;
update_one_process(p, user_tick, system, cpu);
run_local_timers( );
scheduler_tick(user_tick, system);
}
update_process_times( )調(diào)用run_local_timers( )引起TIMER_SOFTIRQ定時(shí)器軟中斷，處理器在隨后的合適的時(shí)機(jī)運(yùn)行軟中斷處理函數(shù)run_timer_softirq，這個(gè)函數(shù)是在init_timers( )函數(shù)中注冊(cè)的：
void __init init_timers(void)
{
timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
(void *)(long)smp_processor_id( ));
register_cpu_notifier(&timers_nb);
open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
}
事實(shí)上軟中斷處理函數(shù)run_timer_softirq( )并沒(méi)有做什么工作，主要的任務(wù)還是通過(guò)調(diào)用__run_timers( )函數(shù)完成的，這個(gè)函數(shù)相當(dāng)于2.4.23內(nèi)核當(dāng)中的run_timer_list( )函數(shù)的功能。
static inline void __run_timers(tvec_base_t *base)
{
struct timer_list *timer;
spin_lock_irq(&base->lock);
/*這里進(jìn)入定時(shí)器處理循環(huán)，利用系統(tǒng)全局jiffies與定時(shí)器基準(zhǔn)jiffies進(jìn)行對(duì)比，如果前者大，則表明有某些定時(shí)器需要進(jìn)行處理了，否則表示所有的定時(shí)器都沒(méi)有超時(shí)*/
while (time_after_eq(jiffies, base->timer_jiffies)) {
struct list_head work_list = LIST_HEAD_INIT(work_list);
struct list_head *head = &work_list;
int index = base->timer_jiffies & TVR_MASK;
/*
在時(shí)間列表數(shù)據(jù)結(jié)構(gòu)當(dāng)中查找是否存在需要進(jìn)行超時(shí)處理的定時(shí)器，時(shí)間列表的數(shù)據(jù)結(jié)構(gòu)定義如下：
typedef struct tvec_s {
struct list_head vec[TVN_SIZE];
} tvec_t;
typedef struct tvec_root_s {
struct list_head vec[TVR_SIZE];
} tvec_root_t;
struct tvec_t_base_s {
spinlock_t lock;
unsigned long timer_jiffies;
struct timer_list *running_timer;
tvec_root_t tv1;
tvec_t tv2;
tvec_t tv3;
tvec_t tv4;
tvec_t tv5;
} ____cacheline_aligned_in_smp;
*/
if (!index &&
(!cascade(base, &base->tv2, INDEX(0))) &&
(!cascade(base, &base->tv3, INDEX(1))) &&
!cascade(base, &base->tv4, INDEX(2)))
cascade(base, &base->tv5, INDEX(3));
++base->timer_jiffies;
list_splice_init(base->tv1.vec + index, &work_list);
repeat:
/*如果當(dāng)前找到的時(shí)間數(shù)組對(duì)應(yīng)的列表不為空，則表明該列表上串連的所有定時(shí)器都已經(jīng)超時(shí)，循環(huán)調(diào)用每個(gè)定時(shí)器的處理函數(shù)，并將其從列表中刪除，直到列表為空為止。*/
if (!list_empty(head)) {
void (*fn)(unsigned long);
unsigned long data;
timer = list_entry(head->next,struct timer_list,entry);
fn = timer->function;
data = timer->data;
list_del(&timer->entry);
set_running_timer(base, timer);
smp_wmb( );
timer->base = NULL;
spin_unlock_irq(&base->lock);
fn(data);
spin_lock_irq(&base->lock);
goto repeat;
}
}
set_running_timer(base, NULL);
spin_unlock_irq(&base->lock);
}
Linux系統(tǒng)調(diào)用的形式與POSIX兼容，也是一套C語(yǔ)言函數(shù)名的集合，如fork( )，read( )等等共221個(gè)。系統(tǒng)調(diào)用是通過(guò)INT 0x80軟中斷調(diào)用進(jìn)入內(nèi)核，然后根據(jù)系統(tǒng)調(diào)用號(hào)分門(mén)別類的進(jìn)行服務(wù)。
系統(tǒng)調(diào)用號(hào)：文件include/asm-i386/unistd.h為每一個(gè)系統(tǒng)調(diào)用規(guī)定了唯一的編號(hào)，這個(gè)編號(hào)與真正的響應(yīng)函數(shù)之間的關(guān)系是利用系統(tǒng)調(diào)用號(hào)為數(shù)組的下標(biāo)，可以在sys_call_table（系統(tǒng)調(diào)用表數(shù)組）中查找對(duì)應(yīng)的響應(yīng)函數(shù)的sys_name的入口地址。
系統(tǒng)調(diào)用表：系統(tǒng)調(diào)用表sys_call_table是一組宏定義，將系統(tǒng)調(diào)用的編號(hào)和相應(yīng)的內(nèi)核系統(tǒng)調(diào)用處理函數(shù)的入口地址綁定。
內(nèi)核宏定義syscallN( )用于系統(tǒng)調(diào)用的格式轉(zhuǎn)換和參數(shù)的傳遞。其中N取0～6之間的任意整數(shù)。參數(shù)個(gè)數(shù)為N的系統(tǒng)調(diào)用由syscallN負(fù)責(zé)格式轉(zhuǎn)換和參數(shù)傳遞。
對(duì)系統(tǒng)調(diào)用的初始化，即是對(duì)INT 0x80的初始化。系統(tǒng)啟動(dòng)時(shí)，匯編子程序setup_idt準(zhǔn)備了256項(xiàng)的idt表。設(shè)置0x80號(hào)軟中斷服務(wù)程序system_call，這個(gè)就是所有系統(tǒng)調(diào)用的總?cè)肟凇?/span>
當(dāng)進(jìn)程需要進(jìn)行系統(tǒng)調(diào)用時(shí)，必須以C語(yǔ)言函數(shù)的形式寫(xiě)一句系統(tǒng)調(diào)用命令。該命令如果已經(jīng)在某個(gè)頭文件中由相應(yīng)的syscallN( )展開(kāi)，則用戶程序必須包含該頭文件。當(dāng)進(jìn)程執(zhí)行到系統(tǒng)調(diào)用命令時(shí)，實(shí)際上執(zhí)行的是syscallN( )展開(kāi)的函數(shù)。系統(tǒng)調(diào)用的參數(shù)由寄存器傳遞，然后執(zhí)行INT 0x80中斷，以內(nèi)核態(tài)進(jìn)入入口地址system_call。
從system_call入口的匯編程序的主要功能是：
l 保存寄存器當(dāng)前值；
l 檢驗(yàn)是否為合法的系統(tǒng)調(diào)用；
l 根據(jù)系統(tǒng)調(diào)用表sys_call_table和EAX持有的系統(tǒng)調(diào)用號(hào)找出并轉(zhuǎn)入系統(tǒng)調(diào)用響應(yīng)函數(shù)；
l 從該響應(yīng)函數(shù)返回后，讓EAX寄存器保存函數(shù)返回值，跳轉(zhuǎn)至ret_from_sys_call（arch/i386/kernel/entry.S）。
以ret_from_sys_call入口的匯編程序段在Linux進(jìn)程管理中起著十分重要的作用。所有系統(tǒng)調(diào)用結(jié)束前，以及大部分中斷服務(wù)程序返回前，都會(huì)跳轉(zhuǎn)至此入口地址。反過(guò)來(lái)，該段程序也不僅僅為系統(tǒng)調(diào)用服務(wù)，它還要處理中斷嵌套、bottom half隊(duì)列、CPU調(diào)度、信號(hào)等事務(wù)。
《Linux內(nèi)核源碼》
《Linux內(nèi)核2.4版源代碼分析大全》