【正文】 負(fù)載很重的系統(tǒng)上有一個很好的交互感是一件很困難的事情，設(shè)計者經(jīng)過研究發(fā)現(xiàn)一味的激勵（ boost）交互任務(wù)并不夠，還需懲罰（ punish）那些需求大于可獲得 CPU時間的進(jìn)程。調(diào)度器通過對用戶睡眠時間和運(yùn)行時間的紀(jì)錄來判斷進(jìn)程是否是交互進(jìn)程，一旦被認(rèn)為是交互進(jìn)程，調(diào)度器會給進(jìn)程很多 獎勵 （ bonus）。 4. 內(nèi)核可搶占 內(nèi)核可搶占可以說是 一個很重要的原因。當(dāng)內(nèi)核進(jìn)程沒有訪問內(nèi)核的關(guān)鍵數(shù)據(jù)，也就是內(nèi)核沒有被加鎖，此時內(nèi)核代碼是可重入的，因此更高優(yōu)先級的進(jìn)程可以在此時中斷正在執(zhí)行的進(jìn)程，從而達(dá)到搶占的目的。 5. 調(diào)度器相關(guān)的負(fù)載均衡 負(fù)載均衡有兩種策略，一種是從別的 CPU上將進(jìn)程遷移過來，稱為 pull；一種是將本 CPU上的進(jìn)程遷移出去，稱為 push。 實驗 實驗： 編寫一個程序，用 fork()創(chuàng)建 2個子進(jìn)程。讓每個進(jìn)程在屏幕上各顯示不同的字符。觀察、記錄并分析屏幕上進(jìn)程調(diào)度的情況。 三、調(diào)度策略 1. 進(jìn)程優(yōu)先級 (1) 優(yōu)先級的計算 優(yōu)先級由兩部分構(gòu)成，一是靜態(tài)優(yōu)先級 static_prio，一是動態(tài)優(yōu)先級 prio。靜態(tài)優(yōu)先級在進(jìn)程創(chuàng)建的時候就被賦值，并且不變（除非用系統(tǒng)調(diào)用改變進(jìn)程的nice值）；而進(jìn)程的動態(tài)優(yōu)先級則是跟 static_prio和sleep_avg有關(guān)。對于實時進(jìn)程的優(yōu)先級在創(chuàng)建的時候就確定了，而且一旦確定以后就不再改變。 三、調(diào)度策略 1. 進(jìn)程優(yōu)先級 (1) 優(yōu)先級的計算 非實時進(jìn)程具體的計算由函數(shù) effecitve_prio() 完成。 sleep_avg和 bonus是一個線性關(guān)系。進(jìn)程的 sleep_avg越大，bonus越大，從而進(jìn)程的動態(tài)優(yōu)先級也就越高。 三、調(diào)度策略 (2) 何時計算優(yōu)先級 a. 創(chuàng)建新進(jìn)程，使用函數(shù) effective_prio()（因為此時進(jìn)程尚未進(jìn)行調(diào)度，沒有 sleep_avg和 interactive_credit可言）； b. 喚醒等待進(jìn)程時，使用函數(shù) recalc_task_prio ()來計算進(jìn)程動態(tài)優(yōu)先級。 c. 進(jìn)程用完時間片以后，被重新插入到 active array或者expired array的時候需要重新計算動態(tài)優(yōu)先級，以便將進(jìn)程插入到隊列的相應(yīng)位置。此時，使用函數(shù) effective_prio()； d. 其他情況，如 IDLE進(jìn)程初始化等時候。 2. 進(jìn)程時間片 (1) 時間片的計算 進(jìn)程的時間片 time_slice是基于進(jìn)程靜態(tài)優(yōu)先級的，靜態(tài)優(yōu)先級越高（值越?。?，時間片就越大。計算時間片是同過函數(shù) task_timeslice()（ kernel/）來完成的。 通過優(yōu)先級來計算時間片的等式為： timeslice = MIN_TIMESLICE + ((MAX_TIMESLICE MIN_TIMESLICE) *(MAX_PRIO1 (p)static_prio) / (MAX_USER_PRIO1)) 2. 進(jìn)程時間片 (2) 何時計算時間片 當(dāng)就緒進(jìn)程的所有進(jìn)程的時間片都是 0的時候，許多操作系統(tǒng)（包括舊版本的 Linux）是使用下面的循環(huán)來給進(jìn)程隊列計算時間片的： for (each task on the system) { recalculate priority。 recalculate timeslice } 導(dǎo)致問題： 循環(huán)可能會花很長時間，而且算法的復(fù)雜度 O(n)； 計算過程中必須給進(jìn)程隊列和 task_struct上鎖，這樣可能導(dǎo)致大量的競爭； 因為計算時間不可預(yù)計，所以可能給實時進(jìn)程帶來問題； 2. 進(jìn)程時間片 (2) 何時計算時間片 在 Kernel ： a. 進(jìn)程創(chuàng)建時，將父進(jìn)程的時間片分一半給子進(jìn)程，同時父進(jìn)程的時間片減半。（ sched_fork）； b. 進(jìn)程用完時間片以后，需要重新計算時間片，并將進(jìn)程插入到相應(yīng)的運(yùn)行隊列。（ scheduler_tick）； c. 進(jìn)程退出時，根據(jù) first_timeslice的值來決定是否將子進(jìn)程的時間片返還給父進(jìn)程。 可見 循環(huán)計算所帶來的幾個問題。 4. 調(diào)度器主函數(shù) schedule()（ kernel/） schedule()是用來挑選出下一個應(yīng)該執(zhí)行的進(jìn)程，并且完成進(jìn)程切換的工作，是進(jìn)程調(diào)度的主要執(zhí)行者，也是操作系統(tǒng) Kernel很重要的一個函數(shù)，它的性能將直接決定操作系統(tǒng)的性能。 (1) 函數(shù)主要流程 兩個重要數(shù)據(jù)： prev和 next prev 當(dāng)前進(jìn)程，也就是即將被切換出 CPU的進(jìn)程 next 下一個進(jìn)程，也就是即將被切換進(jìn) CPU的進(jìn)程 準(zhǔn)備工作 a. 做原子操作方面的檢查（主要是檢查內(nèi)核搶占和內(nèi)核鎖的深度是否一致）； b. 關(guān)閉內(nèi)核搶占（通過函數(shù) preempt_disable()，因為此時將要對內(nèi)核一系列重要數(shù)據(jù)進(jìn)行操作，所以必須將內(nèi)核搶占關(guān)閉； c. 將當(dāng)前進(jìn)程 current賦值給 prev，獲取當(dāng)前 CPU的運(yùn)行隊列 rq，釋放 prev的內(nèi)核鎖（因為即將對 prev做一系列操作），計算prev的運(yùn)行時間（如果是交互進(jìn)程則給予 run_time上的獎勵），給 rq上自旋鎖（防止其他進(jìn)程訪問 rq）； d. 進(jìn)行內(nèi)核的數(shù)據(jù)統(tǒng)計（如上下文切換次數(shù)等），如果 prev處于可中斷狀態(tài)，而且有信號等待處理，則將 prev狀態(tài)置為TASK_RUNNING，否則將 prev從 rq中刪除。（這一部分的代碼主要是因為在進(jìn)程在轉(zhuǎn)入睡眠狀態(tài)時，需要主動調(diào)用 schedule()函數(shù)）； e. 如果 rq中就緒進(jìn)程個數(shù)為 0，而且系統(tǒng)是 SMP，則進(jìn)行負(fù)載均衡的操作，否則將 next置為 idle進(jìn)程，賦值 rqexpired_timestamp = 0，然后直接進(jìn)行進(jìn)程切換。 尋找最高優(yōu)先級進(jìn)程 a. 如果 rq的 active array中進(jìn)程個數(shù)為 0，則將 active array和expired array進(jìn)行切換。具體的過程由以下代碼完成： array = rqactive。 rqactive = rqexpired。 rqexpired = array。 rqexpired_timestamp = 0。 rqbest_expired_prio = MAX_PRIO。 b. 用函數(shù) sched_find_first_bit()找到優(yōu)先級最高的進(jìn)程隊列的偏移量 idx，那么 queue[idx]next即為所找的 next，可以通過以下三行代碼快速完成： idx = sched_find_first_bit(arraybitmap)。 queue = arrayqueue + idx。 next = list_entry(queuenext, task_t, run_list)。 c. 如果 next是從 TASK_INTERRUPTIBLE狀態(tài)中被喚醒的（ actived0），則將進(jìn)程從就緒隊列中刪除，將進(jìn)程在就緒隊列上的等待時間也加在等待時間里面重新計算進(jìn)程的 prio，再根據(jù)新的優(yōu)先級將進(jìn)程插入相應(yīng)就緒隊列。 進(jìn)程切換 a. 如果 prev!=next，則進(jìn)行進(jìn)程切換； b. 進(jìn)行進(jìn)程切換前的準(zhǔn)備：將當(dāng)前時間賦給 nexttimestamp，并且將 rqcurr=next；可見此時的 rqcurr與current不再相同； c. 進(jìn)程切換，包括內(nèi)存、堆棧切換等。具體過程和 Kernel ； 完成進(jìn)程切換后 完成進(jìn)程切換過后，還需要進(jìn)行釋放 prev的 mm，給 rq解鎖，重新給 current獲得內(nèi)核鎖（注意在此時 current=next=rqcurr），使能內(nèi)核搶占；最后檢查 TIF_NEED_RESCHED位，如果已被置位，則重新開始進(jìn)行調(diào)度，重復(fù)上述過程；否則調(diào)度結(jié)束。 作業(yè)（ 10月 14日交） 分析 比有哪些改進(jìn) Q amp。 A