Linux 程序排程原理

   程序排程依據

    排程程式運作時，要在所有可運作狀态的程序中選擇最值得運作的程序投入運作。選擇程序的依據是什麼呢？在每個程序的task_struct結構中有以下四項：policy、priority、counter、rt_priority。這四項是選擇程序的依據。其中，policy是程序的排程政策，用來區分實時程序和普通程序，實時程序優先于普通程序運作；priority是程序(包括實時和普通)的靜态優先級；counter是程序剩餘的時間片，它的起始值就是priority的值；由于counter在後面計算一個處于可運作狀态的程序值得運作的程度goodness時起重要作用，是以，counter也可以看作是程序的動态優先級。rt_priority是實時程序特有的，用于實時程序間的選擇。

Linux用函數goodness()來衡量一個處于可運作狀态的程序值得運作的程度。該函數綜合了以上提到的四項，還結合了一些其他的因素，給每個處于可運作狀态的程序賦予一個權值(weight)，排程程式以這個權值作為選擇程序的唯一依據。關于goodness()的情況在後面将會詳細分析。

程序排程政策

排程程式運作時,要在所有處于可運作狀态的程序之中選擇最值得運作的程序投入運作。選擇程序的依據是什麼呢?在每個程序的task_struct 結構中有這麼四項：

policy, priority , counter, rt_priority

這四項就是排程程式選擇程序的依據.其中,policy是程序的排程政策,用來區分兩種程序-實時和普通；priority是程序(實時和普通)的優先級；counter 是程序剩餘的時間片,它的大小完全由priority決定;rt_priority是實時優先級,這是實時程序所特有的，用于實時程序間的選擇。

首先，Linux 根據policy從整體上區分實時程序和普通程序，因為實時程序和普通程序度排程是不同的，它們兩者之間，實時程序應該先于普通程序而運作，然後，對于同一類型的不同程序，采用不同的标準來選擇程序：

對于普通程序，Linux采用動态優先排程，選擇程序的依據就是程序counter的大小。程序建立時，優先級priority被賦一個初值，一般為0～70之間的數字，這個數字同時也是計數器counter的初值，就是說程序建立時兩者是相等的。字面上看，priority是"優先級"、counter是"計數器"的意思，然而實際上，它們表達的是同一個意思-程序的"時間片"。Priority代表配置設定給該程序的時間片，counter表示該程序剩餘的時間片。在程序運作過程中，counter不斷減少，而priority保持不變，以便在counter變為0的時候（該程序用完了所配置設定的時間片）對counter重新指派。當一個普通程序的時間片用完以後，并不馬上用priority對counter進行指派，隻有所有處于可運作狀态的普通程序的時間片(p->counter==0)都用完了以後，才用priority對counter重新指派，這個普通程序才有了再次被排程的機會。這說明，普通程序運作過程中，counter的減小給了其它程序得以運作的機會，直至counter減為0時才完全放棄對CPU的使用，這就相對于優先級在動态變化，是以稱之為動态優先排程。至于時間片這個概念，和其他不同作業系統一樣的，Linux的時間機關也是"時鐘滴答"，隻是不同作業系統對一個時鐘滴答的定義不同而已（Linux為10ms）。程序的時間片就是指多少個時鐘滴答，比如，若priority為20，則配置設定給該程序的時間片就為20個時鐘滴答，也就是20*10ms=200ms。Linux中某個程序的排程政策(policy)、優先級(priority)等可以作為參數由使用者自己決定，具有相當的靈活性。核心建立新程序時配置設定給程序的時間片預設為200ms(更準确的，應為210ms)，使用者可以通過系統調用改變它。

對于實時程序，Linux采用了兩種排程政策，即FIFO(先來先服務排程)和RR（時間片輪轉排程）。因為實時程序具有一定程度的緊迫性，是以衡量一個實時程序是否應該運作，Linux采用了一個比較固定的标準。實時程序的counter隻是用來表示該程序的剩餘時間片，并不作為衡量它是否值得運作的标準。實時程序的counter隻是用來表示該程序的剩餘時間片，并不作為衡量它是否值得運作的标準，這和普通程序是有差別的。上面已經看到，每個程序有兩個優先級，實時優先級就是用來衡量實時程序是否值得運作的。

這一切看來比較麻煩，但實際上Linux中的實作相當簡單。Linux用函數goodness()來衡量一個處于可運作狀态的程序值得運作的程度。該函數綜合了上面提到的各個方面，給每個處于可運作狀态的程序賦予一個權值(weight)，排程程式以這個權值作為選擇程序的唯一依據。

Linux根據policy的值将程序總體上分為實時程序和普通程序，提供了三種排程算法：一種傳統的Unix排程程式和兩個由POSIX.1b(原名為POSIX.4)作業系統标準所規定的"實時"排程程式。但這種實時隻是軟實時，不滿足諸如中斷等待時間等硬實時要求，隻是保證了當實時程序需要時一定隻把CPU配置設定給實時程序。

非實時程序有兩種優先級，一種是靜态優先級，另一種是動态優先級。實時程序又增加了第三種優先級，實時優先級。優先級是一些簡單的整數，為了決定應該允許哪一個程序使用CPU的資源，用優先級代表相對權值-優先級越高，它得到CPU時間的機會也就越大。

? 靜态優先級(priority)-不随時間而改變，隻能由使用者進行修改。它指明了在被迫和其他程序競争CPU之前，該程序所應該被允許的時間片的最大值（但很可能的，在該時間片耗盡之前，程序就被迫交出了CPU）。

? 動态優先級(counter)-隻要程序擁有CPU，它就随着時間不斷減小；當它小于0時，标記程序重新排程。它指明了在這個時間片中所剩餘的時間量。

? 實時優先級(rt_priority)-指明這個程序自動把CPU交給哪一個其他程序；較高權值的程序總是優先于較低權值的程序。如果一個程序不是實時程序，其優先級就是0，是以實時程序總是優先于非實時程序的（但實際上，實時程序也會主動放棄CPU）。

當policy分别為以下值時：

1) SCHED_OTHER：這是普通的使用者程序，程序的預設類型，采用動态優先排程政策，選擇程序的依據主要是根據程序goodness值的大小。這種程序在運作時，可以被高goodness值的程序搶先。

2) SCHED_FIFO：這是一種實時程序，遵守POSIX1.b标準的FIFO(先入先出)排程規則。它會一直運作，直到有一個程序因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個具有更高rt_priority的實時程序搶先。在Linux實作中，SCHED_FIFO程序仍然擁有時間片-隻有當時間片用完時它們才被迫釋放CPU。是以，如同POSIX1.b一樣，這樣的程序就象沒有時間片(不是采用分時)一樣運作。Linux中程序仍然保持對其時間片的記錄（不修改counter）主要是為了實作的友善，同時避免在排程代碼的關鍵路徑上出現條件判斷語句 if (!(current->policy&SCHED_FIFO)){...}-要知道，其他大量非FIFO程序都需要記錄時間片，這種多餘的檢測隻會浪費CPU資源。（一種優化措施，不該将執行時間占10%的代碼的運作時間減少到50%；而是将執行時間占90%的代碼的運作時間減少到95%。0.9+0.1*0.5=0.95>0.1+0.9*0.9=0.91）

3) SCHED_RR：這也是一種實時程序，遵守POSIX1.b标準的RR(循環round-robin)排程規則。除了時間片有些不同外，這種政策與SCHED_FIFO類似。當SCHED_RR程序的時間片用完後，就被放到SCHED_FIFO和SCHED_RR隊列的末尾。

隻要系統中有一個實時程序在運作，則任何SCHED_OTHER程序都不能在任何CPU運作。每個實時程序有一個rt_priority，是以，可以按照rt_priority在所有SCHED_RR程序之間配置設定CPU。其作用與SCHED_OTHER程序的priority作用一樣。隻有root使用者能夠用系統調用sched_setscheduler，來改變目前程序的類型(sys_nice,sys_setpriority)。

此外，核心還定義了SCHED_YIELD，這并不是一種排程政策，而是截取排程政策的一個附加位。如同前面說明的一樣，如果有其他程序需要CPU，它就提示排程程式釋放CPU。特别要注意的就是這甚至會引起實時程序把CPU釋放給非實時程序。

主要的程序排程的函數分析

真正執行排程的函數是schedule(void),它選擇一個最合适的程序執行，并且真正進行上下文切換，使得選中的程序得以執行。而reschedule_idle(struct task_struct *p)的作用是為程序選擇一個合适的CPU來執行，如果它選中了某個CPU，則将該CPU上目前運作程序的need_resched标志置為1,然後向它發出一個重新排程的處理機間中斷，使得選中的CPU能夠在中斷處理傳回時執行schedule函數，真正排程程序p在CPU上執行。在schedule()和reschedule_idle()中調用了goodness()函數。goodness()函數用來衡量一個處于可運作狀态的程序值得運作的程度。此外，在schedule()函數中還調用了schedule_tail()函數;在reschedule_idle()函數中還調用了reschedule_idle_slow()。這些函數的實作對了解SMP的排程非常重要，下面一一分析這些函數。先給出每個函數的主要流程圖，然後給出源代碼，并加注釋。

goodness()函數分析

goodness()函數計算一個處于可運作狀态的程序值得運作的程度。一個任務的goodness是以下因素的函數：正在運作的任務、想要運作的任務、目前的CPU。goodness傳回下面兩類值中的一個：1000以下或者1000以上。1000或者1000以上的值隻能賦給"實時"程序，從0到999的值隻能賦給普通程序。實際上，在單處理器情況下，普通程序的goodness值隻使用這個範圍底部的一部分，從0到41。在SMP情況下，SMP模式會優先照顧等待同一個處理器的程序。不過，不管是UP還是SMP，實時程序的goodness值的範圍是從1001到1099。

goodness()函數其實是不會傳回-1000的，也不會傳回其他負值。由于idle程序的counter值為負，是以如果使用idle程序作為參數調用goodness，就會傳回負值，但這是不會發生的。

goodness()是個簡單的函數，但是它是linux排程程式不可缺少的部分。運作隊列中的每個程序每次執行schedule時都要排程它，是以它的執行速度必須很快。

//在/kernel/sched.c中

static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)

{ int weight;

if (p->policy != SCHED_OTHER) {/*如果是實時程序，則*/

weight = 1000 + p->rt_priority;

goto out;

}

/* 将counter的值賦給weight，這就給了程序一個大概的權值，counter中的值表示程序在一個時間片内，剩下要運作的時間.*/

weight = p->counter;

if (!weight) /* weight==0,表示該程序的時間片已經用完，則直接轉到标号out*/

#ifdef __SMP__

/*在SMP情況下，如果程序将要運作的CPU與程序上次運作的CPU是一樣的，則最有利，是以，假如程序上次運作的CPU與目前CPU一緻的話，權值加上PROC_CHANGE_PENALTY，這個宏定義為20。*/

if (p->processor == this_cpu)

weight += PROC_CHANGE_PENALTY;

#endif

if (p->mm == this_mm) /*程序p與目前運作程序，是同一個程序的不同線程，或者是共享位址空間的不同程序，優先選擇，權值加1*/

weight += 1;

weight += p->priority; /* 權值加上程序的優先級*/

out:

return weight; /* 傳回值作為程序排程的唯一依據，誰的權值大，就排程誰運作*/

schedule()函數分析

schedule()函數的作用是，選擇一個合适的程序在CPU上執行，它僅僅根據'goodness'來工作。對于SMP情況，除了計算每個程序的權重平均運作時間外，其他與SMP相關的部分主要由goodness()函數來展現。

Schedule()函數的主要流程圖如下：

流程：

①将prev和next設定為schedule最感興趣的兩個程序：其中一個是在調用schedule時正在運作的程序(prev)，另外一個應該是接着就給予CPU的程序（next）。注意：prev和next可能是相同的-schedule可以重新排程已經獲得cpu的程序.

②中斷處理程式運作"下半部分".

③核心實時系統部分的實作，循環排程程式（SCHED_RR）通過移動"耗盡的"RR程序-已經用完其時間片的程序-到隊列末尾，這樣具有相同優先級的其他RR程序就可以獲得CPU了。同時，這補充了耗盡程序的時間片。

④由于代碼的其他部分已經決定了程序必須被移進或移出TASK_RUNNING狀态，是以會經常使用schedule，例如，如果程序正在等待的硬體條件已經發生，是以如果必要，這個switch會改變程序的狀态。如果程序已經處于TASK_RUNNING狀态，它就無需處理了。如果它是可以中斷的（等待信号），并且信号已經到達了程序，就傳回TASK_RUNNING狀态。在是以其他情況下（例如，程序已經處于TASK_UNINTERRUPTIBLE狀态了），應該從運作隊列中将程序移走。

⑤将p初始化為運作隊列的第一個任務；p會周遊隊列中的所有任務。

⑥c記錄了運作隊列中所有程序最好的"goodness"-具有最好"goodness"的程序是最易獲得CPU的程序。goodness的值越高越好。

⑦周遊執行任務連結清單，跟蹤具有最好goodness的程序。

⑧這個循環中隻考慮了唯一一個可以排程的程序。在SMP模式下，隻有任務不在cpu上運作時，即can_schedule宏傳回為真時，才會考慮該任務。在UP情況下，can_schedule宏傳回恒為真.

⑨如果循環結束後，得到c的值為0。說明運作隊列中的所有程序的goodness值都為0。goodness的值為0,意味着程序已經用完它的時間片，或者它已經明确說明要釋放CPU。在這種情況下，schedule要重新計算程序的counter；新counter的值是原來值的一半加上程序的靜态優先級（priortiy），除非程序已經釋放CPU，否則原來counter的值為0。是以，schedule通常隻是把counter初始化為靜态優先級。（中斷處理程式和由另一個處理器引起的分支在schedule搜尋goodness最大值時都将增加此循環中的計數器，是以由于這個原因計數器可能不會為0。顯然，這很罕見。）在counter的值計算完成後，重新開始執行這個循環，找具有最大goodness的任務。

⑩如果schedule已經選擇了一個不同于前面正在執行的程序來排程，那麼就必須挂起原來的程序并允許新的程序運作。這時調用switch_to來進行切換。

    代碼摘自linux/kernel/sched.c：

asmlinkage void schedule(void)

{

struct schedule_data * sched_data;

struct task_struct *prev, *next, *p;

int this_cpu, c;

if (tq_scheduler) /*tq_scheduler是一個特殊的隊列，隻在排程程式運作時得到執行，其目的是為了進行擴充，用來支援系統中多于32個的任務隊列*/

goto handle_tq_scheduler;

tq_scheduler_back:

prev = current;

this_cpu = prev->processor;

if (in_interrupt()) /*判斷schedule是否在中斷進行中執行，如果是在中斷中執行，就說明發生了錯誤，會引發OOPS錯誤*/

goto scheduling_in_interrupt;

release_kernel_lock(prev, this_cpu); /*釋放全局核心鎖，并開this_cpu的中斷，主要是在進行程序切換前釋放核心鎖，否則，若不釋放，切換後的程序也要獲得核心鎖，就會發生死鎖*/

/*檢測是否有中斷下半部需要處理*/

if (bh_mask & bh_active)

goto handle_bh;

handle_bh_back:

/*對于aligned_data[this_cpu].schedule_data的讀寫不需要用鎖保護，因為，每個CPU上任意時刻隻有一個程序運作*/

sched_data = & aligned_data[this_cpu].schedule_data;/*取得本地cpu上的排程資料*/

spin_lock_irq(&runqueue_lock);/*要開始操作要運作程序隊列，不允許打斷，故鎖住運作隊列，并且同時關中斷*/

/*将一個時間片用完的SCHED_RR程序放到隊列的末尾*/

if (prev->policy == SCHED_RR)

goto move_rr_last;

move_rr_back:

switch (prev->state) {

case TASK_INTERRUPTIBLE: /*此狀态表明程序可以被信号中斷*/

if (signal_pending(prev)) {/*如果該程序有未處理的信号*/

prev->state = TASK_RUNNING;

break;

default:

del_from_runqueue(prev);

case TASK_RUNNING:

prev->need_resched = 0;

repeat_schedule: /*真正找合适的程序*/

p = init_task.next_run;

/* Default process to select.. */

next = idle_task(this_cpu); /*預設選擇空閑程序*/

c = -1000;

if (prev->state == TASK_RUNNING)

goto still_running;

still_running_back:

while (p != &init_task) {

if (can_schedule(p)) { /*程序p不占用cpu*/

int weight = goodness(prev, p, this_cpu);

if (weight > c)

c = weight, next = p;

p = p->next_run;

/*c中存放最大的goodness值*/

if (!c) /*如果goodness（prev,p,this_cpu）函數傳回的是0,表示程序p剩餘的運作時間為0,則要重新計算*/

goto recalculate;

/*到這一點，已經确定了要排程執行的程序*/

/*記錄排程選擇的情況*/

sched_data->curr = next;

next->has_cpu = 1;

next->processor = this_cpu;

spin_unlock_irq(&runqueue_lock); /*對運作隊列資料結構操作完成，釋放運作隊列鎖，并打開中斷*/

if (prev == next) /*如果選中的程序和原來運作的程序是同一個*/

goto same_process;

/*計算該程序在其生命周期裡占有cpu的平均時間：avg_slice。這是權重平均，程序近期的活動遠比很久以前的活動權值大。這個值将在reschedule_idle中用來決定是否将程序調入到另一個CPU中。是以，在UP情況下，它不需要而且也不會被計算。*/

cycles_t t, this_slice;

t = get_cycles();

this_slice = t - sched_data->last_schedule;

sched_data->last_schedule = t;

/*計算程序的平均運作時間*/

prev->avg_slice = (this_slice*1 + prev->avg_slice*1)/2;

#endif /* __SMP__ */

kstat.context_switch++;

get_mmu_context(next);

switch_to(prev, next, prev); /*切換到選中的程序執行*/

__schedule_tail(prev); /*該函數調用的作用是：考慮将目前被切換下來的程序，放到别的CPU上運作*/

same_process:

reacquire_kernel_lock(current); /*重新獲得核心鎖*/

return;

recalculate:

struct task_struct *p;

spin_unlock_irq(&runqueue_lock);

read_lock(&tasklist_lock); /*tasklist可以允許多個讀者讀，但當有一個寫者時，不運作有其他讀者或寫者*/

for_each_task(p) /*對于每個重新計算p->counter*/

p->counter = (p->counter >> 1) + p->priority;

read_unlock(&tasklist_lock);

spin_lock_irq(&runqueue_lock);

goto repeat_schedule;

still_running:

c = prev_goodness(prev, prev, this_cpu);

next = prev;

goto still_running_back;

handle_bh:/*進行中斷下半部*/

do_bottom_half();

goto handle_bh_back;

handle_tq_scheduler:/*處理tq_scheduler中的任務*/

run_task_queue(&tq_scheduler);

goto tq_scheduler_back;

move_rr_last:/*将一個時間片用完的程序放到運作隊列的末尾*/

if (!prev->counter) {

prev->counter = prev->priority;

move_last_runqueue(prev);

goto move_rr_back;

scheduling_in_interrupt: /*處理在中斷中排程的情況，産生一個錯誤*/

printk("Scheduling in interrupt/n");

*(int *)0 = 0; /*向一個非法位址寫,産生錯譯*/

reschedule_idle()函數分析

當已經不在運作隊列中的程序被喚醒時，wake_up_process(struct task_struct * p)将調用reschedule_idle，程序是作為p而被傳遞進reschedule_idle中的。這個函數試圖把新近喚醒的程序在一個最合适的CPU上運作。

reschedule_idle()函數主要針對SMP系統，不過，在該函數中調用了reschedule_idle_slow()中，在reschedule_idle_slow()中，存在一些針對UP的代碼。

在reschedule_idle()中使用goodness()，目的是用來預測在我們發送到的CPU上運作schedule()的效果。通過預測未來執行schedule()的效果，可以在任務被喚醒時，選擇最好的CPU去運作。reschedule_idle()的最後一個目标是：讓選中的CPU上調用schedule()，使得被喚醒的任務能在該CPU上重新排程運作。這是如何做的的呢？如果選擇到的最好CPU不是目前CPU，就可以通過CPU間消息傳遞方法（在i386中，是SMP-IPI中斷），向該CPU發送一個重新排程的事件。如果就是目前CPU，就可以直接将目前運作程序的need_resched标志置為1，在随後的時鐘中斷結束時引發排程。

Reschedule_idle的主要流程：

以下代碼摘自linux/kernel/sched.c

static void reschedule_idle(struct task_struct * p)

/*這個函數代碼分兩部分。第一部分：快速判斷是否需要找一個合适的CPU讓程序p運作，如果不需要直接傳回；這部分代碼，隻是在SMP情況下才會執行。第二部分代碼調用reschedule_idle_slow(),真正去找一個合适的CPU讓程序p執行。*/

int cpu = smp_processor_id();

/*檢查是否值得找一個合适的CPU讓p執行,如果不值得，則直接傳回*/

if ((p->processor == cpu) && related(cpu_curr(cpu), p))

reschedule_idle_slow(p);

宏related(p1,p2)的分析：

其中宏related(p1,p2)定義為：

摘自：kernel/sched.c

#define related(p1,p2) (((p1)->lock_depth >= 0) && (p2)->lock_depth >= 0) && (((p2)->policy== SCHED_OTHER) && ((p1)->avg_slice < cacheflush_time))

當以下三種條件同時滿足時，該宏傳回為真：

①(p1)->lock_depth >= 0) && (p2)->lock_depth >= 0)為真，表明程序p1和p2都在控制着，或想要控制核心鎖，說明這兩個程序存在互相依賴關系，則不管這兩個程序生存于何處，都不可能同時運作；

②程序p1的的平均運作時間小于清空本地高速緩存的時間（cacheflush_time），cacheflush_time在系統啟動時被指派為cpu_hz/1024*cachesize/5000，其中cpu_hz為CPU的時鐘頻率，cachesize為高速緩存的大小；

③程序p2是一個普通程序；

從總體上來說，宏related(p1,p2)主要檢測程序p1和p2是否存在互相依賴關系。如果依賴關系存在，則不管這兩個程序生存于何處，都不可能同時運作。宏related(p1,p2)傳回真，表明沒有必要找另一個合适的CPU讓程序p2執行。

reschedule_idle_slow()函數分析

reschedule_idle_slow(struct task_struct * p)的目标是試圖找出一個合适的CPU來運作程序p。

流程圖： 

   SMP情況下流程：

①先檢查p程序上一次運作的cpu是否空閑，如果空閑，這是最好的cpu，直接傳回；

②找一個合适的cpu，檢視SMP中的每個CPU上運作的程序，與p程序相比的搶先goodness，把具有最高的搶先goodness值的程序記錄在target_task中，該程序運作的cpu為最合适的CPU。但是，如果在檢查的過程中，發現某個cpu上運作的程序與程序p是相關的，即related宏傳回為真，表明沒有必要找一個CPU讓程序運作，直接轉到标号out_no_target執行；

③如target_task為空，說明沒有找到合适的cpu，直接轉到标号out_no_target執行。

④如果target_task不為空，則說明找到了合适的cpu，是以将target_task->need_resched置為1,如果運作target_task的cpu不是reschedule_idle_slow運作的cpu，則向運作target_task的cpu發送一個中斷，讓它重新排程；

⑤out_no_target後的語句，就直接傳回；

UP情況下流程：

檢查p能否搶先cpu上運作的程序，如果能搶先（即preemtion_goodness(task,p,this_cpu)>0），則将cpu上目前程序的need_resched域置為1，引發排程。

以下代碼摘自：linux/kernel/sched.c

static inline void reschedule_idle_slow(struct task_struct * p)

/*在SMP中，盡力找一個最合适的CPU讓程序p執行。這個合适的CPU可能是空閑CPU，但也有可能不是空閑CPU。隻要程序p的goodness值比CPU上運作的目前程序的goodness值要高，就可以搶先在該CPU上運作的程序。當然，在選擇合适的CPU時，是選擇程序p與該CPU上運作程序的goodness的值相差最大的CPU。*/

int this_cpu = smp_processor_id(), target_cpu;

struct task_struct *tsk, *target_tsk;

int cpu, best_cpu, weight, best_weight, i;

unsigned long flags;

best_weight = 0;

/*要讀寫運作隊列，必須先獲得運作隊列自旋鎖，并且確定關中斷*/

spin_lock_irqsave(&runqueue_lock, flags);

best_cpu = p->processor;

target_tsk = idle_task(best_cpu); /*idle_task（）得到當該cpu的空閑程序*/

if (cpu_curr(best_cpu) == target_tsk) /*程序上一次運作的cpu是空閑的*/

goto send_now;

target_tsk = NULL;

for (i = 0; i < smp_num_cpus; i++) {

cpu = cpu_logical_map(i);

tsk = cpu_curr(cpu);

if (related(tsk, p)) /*如果tak和p相依賴，則這兩個程序幾乎不可能同時運作，是以，不需要找在空閑cpu讓p執行*/

goto out_no_target;

/*計算p搶先tsk的goodness,preemption_goodness(),實際上是計算兩個程序的goodness()的內插補點*/

weight = preemption_goodness(tsk, p, cpu);

if (weight > best_weight) {

best_weight = weight;

target_tsk = tsk;

/*以上for循環執行完後，target_task應該是最合适的cpu上運作的程序*/

if (!target_tsk) /*如果沒有合适的cpu*/

send_now:

target_cpu = target_tsk->processor;

target_tsk->need_resched = 1;

/*釋放運作隊列鎖，并恢複中斷标志，注意：不一定是開中斷，恢複執行spin_lock_irqsave前的狀态*/

spin_unlock_irqrestore(&runqueue_lock, flags);

if (target_cpu != this_cpu) /*如果不是是目前排程程式運作的cpu，則*/

smp_send_reschedule(target_cpu);/*向選擇的CPU發送一個IPI,使得該CPU上能進行排程*/

out_no_target:

/*沒有找到合适的CPU，釋放運作隊列鎖，并恢複中斷标志*/

#else

/*處理單CPU的情況，因為隻有一個CPU，是以不需要選擇了，隻需要看是否值得搶先目前正在運作的程序就可以了。*/

int this_cpu = smp_processor_id();

struct task_struct *tsk;

tsk = current;

if (preemption_goodness(tsk, p, this_cpu) > 0)

tsk->need_resched = 1;

這裡涉及處理機間通信/中斷，我們将在第三部分詳細介紹，這裡隻讨論與處理機排程有關的部分。Intel多處理規範MP的核心就是進階可程式設計中斷控制器（Advanced Programmable Interrupt Controllers，APIC）的使用。CPU通過彼此發送中斷來完成它們之間的通信。通過給中斷附加動作，不同的CPU可以在某種程度廣彼此進行控制。每個CPU有自己的APIC（成為那個CPU的本地APIC），并且還有一個I／O APIC來處理由I／O裝置引起的中斷。在普通的多處理器系統中，I／O APIC中斷控制器晶片組的作用。

void smp_send_reschedule(int cpu)

send_IPI_single(cpu, RESCHEDULE_VECTOR);

這個函數隻有一行，它僅僅是給其ID以參數形式給出的目标CPU發送一個中斷。函數用CPU ID和RESCHEDULE＿VECTOR向量調用send＿IPI＿single函數。RESCHEDULE_VECTOR與其他CPU中斷向量是一起在arch/i386/kernel/irq.h中被定義。

#define RESCHEDULE_VECTOR 0x30

#define INVALIDATE_TLB_VECTOR 0x31

#define STOP_CPU_VECTOR 0x40

#define LOCAL_TIMER_VECTOR 0x41

#define CALL_FUNCTION_VECTOR 0x50

static inline void send_IPI_single(int dest, int vector)

send＿IPI＿single函數發送一個IPI--那是Intel對處理器問中斷（Interprocessor interruPt）的稱呼--給指定的目的CPU。在這一行，核心以相當低級的方式與發送CPU的本地APIC對話。

unsigned long cfg;

#if FORCE_APIC_SERIALIZATION

__save_flags(flags);

__cli();

cfg = __prepare_ICR2(dest);

得到中斷指令寄存器（ICR）上半部分的内容--本地APIC就是通過這個寄存器進行程式設計的--不過它的目的資訊段要被設定為dest。盡管．＿prepare＿ICRZ裡使用了"2"，CPU實際上隻有一個ICR，而不是兩個。但是它是一個64位寄存器，核心更願意把它看作是兩個32位寄存器--在核心代碼裡，"ICR"表示這個寄存器的低端32位，是以"ICR2"就表示高端32位。我們想要設定的目的資訊段就在高端32位，即ICR2裡。

apic_write(APIC_ICR2, cfg);

把修改過的資訊寫回ICR。現在ICR知道了目的CPU。

cfg = __prepare_ICR(0, vector);

調用＿prepare＿ICR來設定我們想要發送給目的CPU的中斷向量（注意沒有什麼措施能夠保證目的CPU不是目前CPU--ICR完全能夠發送一個IPI給它自己的CPU。盡管這樣，沒有任何理由要這樣做）。

apic_write(APIC_ICR, cfg);

通過往ICR裡寫入新的配置來發送中斷。

__restore_flags(flags);

schedule_tail()函數分析

顧名思義，該函數的作用是執行schedule()函數的一些掃尾工作。在SMP情況下，如果失去CPU的程序,其狀态是TASK_RUNNING,并且不是空閑程序，則調用reschedule_idle()，找一個合适的CPU去運作。并且将失去CPU的程序的has_cpu域置為0。并且為保證處理器一緻性，調用wmb()來has_cpu=0這個操作不會被提前執行。

代碼摘自：linux/kernel/sched.c：

static inline void __schedule_tail (struct task_struct *prev)

if ((prev->state == TASK_RUNNING) &&(prev != idle_task(smp_processor_id())))

reschedule_idle(prev);

wmb(); /*根據處理器一緻性（PO）,保證讀、寫操作的順序*/

prev->has_cpu = 0;

此外，源碼是最好的文檔，看看kernel/sched.c

#ifndef __alpha__

/*

* This has been replaced by sys_setpriority. Maybe it should be

* moved into the arch dependent tree for those ports that require

* it for backward compatibility?

*/

asmlinkage int sys_nice(int increment)

unsigned long newprio;

int increase = 0;

* Setpriority might change our priority at the same moment.

* We don't have to worry. Conceptually one call occurs first

* and we have a single winner.

newprio = increment;

if (increment < 0) {

if (!capable(CAP_SYS_NICE))

return -EPERM;

newprio = -increment;

increase = 1;

if (newprio > 40)

newprio = 40;

* do a "normalization" of the priority (traditionally

* Unix nice values are -20 to 20; Linux doesn't really

* use that kind of thing, but uses the length of the

* timeslice instead (default 210 ms). The rounding is

* why we want to avoid negative values.

newprio = (newprio * DEF_PRIORITY + 10) / 20;

increment = newprio;

if (increase)

increment = -increment;

* Current->priority can change between this point

* and the assignment. We are assigning not doing add/subs

* so thats ok. Conceptually a process might just instantaneously

* read the value we stomp over. I don't think that is an issue

* unless posix makes it one. If so we can loop on changes

* to current->priority.

newprio = current->priority - increment;

if ((signed) newprio < 1)

newprio = 1;

if (newprio > DEF_PRIORITY*2)

newprio = DEF_PRIORITY*2;

current->priority = newprio;

return 0;