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